树型数据结构.pptVIP

数据结构 孙超 Email：schschschsch@163.com 主要内容 以树的概念为基础的数据结构： 堆 线段树 树状数组 二叉查找树 堆 使用堆的目的 堆的定义 堆的操作 取最优值 插入元素 删除元素 建立一个堆 堆的应用 使用堆的目的 空间目的：无需附加空间 时间目的： 取最优值 O(1) 插入元素 O(logn) 删除元素 O(logn) 堆的定义 堆是一颗完全二叉树 堆要么是空树要么满足如下条件： 根节点小于（或大于）子节点 左子树和右子树都是堆 可以看到，堆是递归定义的数据结构。 堆的定义(续) 对于完全二叉树，我们可以直接用数组存储，因此堆还有另一种定义方式 如果对于一个数组A。 满足对于任意的i有: A[i]≥A[i*2] 且 A[i]≥A[i*2+1] 则称A为一个堆(最大堆)。 实际上，堆都是采用数组(根为1)实现的。 堆的实例 一个最大堆的实例 ，对应在数组中的 存储为： (78, 46, 67, 44, 22, 50, 7, 35, 10) 堆的操作 一个基本的堆可以 实现一下几个操作： 取最优值 插入元素 删除元素 建立一个堆 取最优值 根据前面的定义可以简单的发现，堆中的最大（小）元素就是第1个元素，因此我们只需要给出第一个元素即可。 代码如下： function getmax begin getmax:=heap[1]; end 很显然，它的时间复杂度为 O(1) 插入元素 先将元素插入到最后一个位置， 但是，插入后，有可能破坏了堆的结构，因此，我们需要对堆进行调整。使得其能够满足堆的定义。这我们通过一个siftup过程来实现。 siftup过程 siftup过程的作用就是将指定的元素向上调整到合适的位置，代码如下： procedure siftup(i:integer); var x,t,u:integer; begin x:=heap[i]; t:=i; u:=t div 2; while (u0) do begin if x=heap[u] then break; heap[t]:=heap[u]; t:=u; u:=t div 2; end; heap[t]:=x; end; 堆的插入 插入操作的时间复杂度 考虑到一个N个节点的完全二叉数高度为O(logN)，因此，插入操作的调整时间复杂度为O(logN) 删除元素 首先考虑删除最后一个元素，我们直接删去[heap(n)]即可。 再考虑删去第一个元素，我们先将它和最后一个交换，再删去。但是，交换后，有可能破坏了堆的结构，因此，我们需要对堆进行调整。使得其能够满足堆的定义。这我们通过一个siftdown过程来实现。 siftdown过程 procedure siftdown(n,i:integer); var x,t,u:integer; begin x:=heap[i]; t:=i; u:=t*2; while (u=n) do begin if heap[u+1]heap[u] then u:=u+1; if x=heap[u] then break; heap[t]:=heap[u]; t:=u; u:=t*2; end; heap[t]:=x; end; 堆的删除 任意位置的元素的删除 对于堆中央的元素的删除，也是采用交换的方法，但是调整的时候，既要考虑siftdown,也要考虑siftup。 删除操作的时间复杂度 易知，删除操作的时间复杂度和插入操作是一样的，也为O(logN)。 建立一个堆 现在给定N个元素，要建立一个堆，怎么办？ 将N个元素一个一个插入，每个时间复杂度为O(logN),总时间为 O(NlogN)。 还不如直接排序。 怎么降低复杂度呢？ 建立一个堆(续) 假设一个节点的左右子树都已经是堆了，那么只要将这个节点向下调整到适当位置即可。 于是我们可以一步一步的使用siftdown过程来完成建堆。 建堆的代码 procedure buildheap(n:integer); var i:integer; begin for i:=n div 2 downto 1 do siftdown(i,n); end; 建堆的时间复杂度分析 显然buildheap的时间就是shiftdown的时间代价之和。 其中1/2的叶子节点不需移动。 1/4的节点最多移动1层 1/8的节点最多移动2层 ... 所以总的时间复杂度： 可以知道，建堆操作的时间复杂度为O(n) 。 堆的应用 Dijkstra, Prim算法的优化 堆排序(Heapsort) … 经常在模拟题中出现，可以把某些操作的