第6章_堆排序_算法分析与设计_杭电_褚一平

1、46.1 堆(二叉)堆数据结构是一种数组对象，它可以被视为一颗完全二叉树，树中每个节点和数组中存放该节点值的那个元素对应。如果表示堆的数组为A，那么树的根为A1。表示堆的数组A是一个具有两个属性的对象：length(A)是数组中的元素个数，heap-size(A)是存放在A中的堆的元素个数；Aheap-size(A)之后的元素都不属于相应的堆。也就是：Heap-size(A) Ai4 then largest l5 else largest i6 If r heap-sizeA and Ar Alargest7 then largest r8 If largest i9 then exchan

2、ge AiAlargest10 MAX-HEAPIFY(A, largest)86.1 MAX-HEAPIFY过程96.1 MAX-HEAPIFY过程106.1 MAX-HEAPIFY过程116.2 MAX-HEAPIFY时间当MAX-HEAPIFY作用在一棵以节点i为根的，大小为n的子树上时，其运行时间为调整元素Ai，ALEFT(i)和ARIGHT(i)的关系时所用时间(1)，再加上对以i的某个子结点为根的子树递归调用MAX-HEAPIFY所需的时间。i结点的子树大小至多为2n/3，那么MAX-HEAPFY的运行时间为：T(n) T(2n/3) + (1)根据主定理，该递归式的解为T(n)

3、(lgn)126.3 建堆我们可以自底向上的用MAX-HEAPIFY来将一个数组A1.n变成一个最大堆。过程BUILD-MAX-HEAP对树中的每一个其他节点都调用一次MAX-HEAPIFY。BUILD-MAX-HEAP(A)1 heap-sizeA lengthAdo MAX-HEAPIFY(A,i)2 for i length A / 2 downto 113建堆过程14建堆过程15建堆过程16建堆过程17建堆过程18建堆过程19BUILD-MAX-HEAP正确性为了证明BUILD-MAX-HEAP的正确性，我们使用如下的循环不变式：在第23行中for循环的每一次迭代开始时，节点i+1，i

4、+2， n都是一个最大堆的根。我们需要证明在第一次循环迭代之前，这个不变式已为真。每次循环迭代都能保持此不变式，并且在循环结束时这个不变式会提供一个很有用的属性来显示程序的正确性。20BUILD-MAX-HEAP正确性也是平凡最大堆的根。保持：要证明每次迭代都保持了循环不变式，注意到结点i的子结点的编号均比i大，于是，根据循环不变式，这些子结点都是最大堆的根。这也是调用函数MAX-HEAPIFY(A,i)，以使结点i成为最大堆的根的前提条件。此外，MAX-HEAPFY的调用保持了结点i+1,i+2,n为最大堆的性质。在for循环中递减i，即为下一次迭代重新建立了循环不等式。初始化：在第一轮循环

5、迭代之前，i n / 2 。结点 n / 2 1，n / 2 2 ，n都是叶结点，21BUILD-MAX-HEAP正确性终止：过程终止时，i=0.根据循环不等式，我们知道结点1，2，n中，每个都是最大堆的根，特别的，结点1就是一个最大堆的根。我们可以这样来计算BUILD-MAX-HEAP运行时间的一个简单上界：每次调用MAX-HEAPFY的时间为O(lgn)，共有O(n)次调用，故运行时间为O(nlgn)。这个界尽管是对的，但是从渐近意义上讲不够紧确。 h 2O n O ( h ) O n 2 O n hh O ( n )222BUILD-MAX-HEAP精确上界MAX-HEAPIFY作用在高

6、度为h的结点上的时间为O(h)，我们可以将BUILD-MAX-HEAP的代价表达为上确界将x=1/2代入几何级数的微分来计算(A.8)，则于是，BUILD-MAX-HEAP的运行时间的界为：hlg nh 0lg n h 0 2nh 12 21 / 2(1 1 / 2 )h 0hhhhh 0 2lg n h 0236.4 堆排序算法开始时，堆排序算法先后用BUILD-MAX-HEAP将输入数组A1.n构造成一个最大堆，因为数组中最大元素在A1，可以通过把它与An互换来达到最终正确的位置。接下来，如果从堆中去掉结点n，可以很容易地将A1.n-1建成最大堆。原来根的子女仍是最大堆，而新的根元素可能违

7、背了最大堆性质。这时调用MAX-HEAPIFY(A,1)就可以保持这一性质，在A1.(n-1)中构建出最大堆。246.4 堆排序算法HEAPSORT(A)1 BUILD-MAX-HEAP(A)2 for i lengthA downto 23 do exchange A1Ai4 heap-sizeAheap-sizeA-15 MAX-HEAPIFY(A,1)HEAPSORT过程的时间代价为O(nlgn)，其中调用BUILD-MAX-HEAP的时间为O(n)，n次MAX-HEAPIFY调用中每一次的时间代价为O(lgn)。256.4 优先级队列堆排序的应用：（最大/最小）优先级队列作业调度：找出

8、优先级最高的、插入作业、调整优先级优先级队列是一种用来维护由一组元素构成的集合S的数据结构，这一组元素中的每一个都有一个关键字key。一个最大优先级队列支持以下操作：INSERT(S,x)：把元素x插入集合SMAXIMUM(S)：返回S中具有最大关键字的元素EXTRACT-MAX(S)：去掉并返回S中的具有最大关键字的元素INCREASE-KEY(S,x,k)：将元素x的关键字的值增加到k，这里k值不能小于x的原关键字的值。26优先级队列的操作程序HEAP-MAXIMUM用(1)时间实现了MAXIMUMHEAP-MAXIMUM(A)return A1程序HEAP-EXTRACT-MAX实现了E

9、XTRACT-MAXHEAP-EXTRACT-MAX(A)if heap-sizeA1then error ”heap underflow”maxA1A1Aheap-sizeAheap-sizeAheap-sizeA 1MAX-HEAPIFY(A,1)return max27优先级队列的操作程序HEAP-INCREASE-KEY实现了INCREASE-KEY操作。在优先级队列中关键字值需要增加的元素由对应数组的下标i来标识。该过程首先将元素Ai的关键字值更新为新的值。由于增大Ai的关键字可能会违反最大堆性质，因此在从本结点往根移动的路径上，为新增大的关键字寻找合适的位置。在移动的过程中，此元素不断地和其父母相比，如果此元素的关键字较大，则交换他们的关键字且继续移动。当元素的关键字小于其父母时，最大堆性质成立，程序终止HEAP-INCREASE-KEY(A,i,key)1 if key 1 and APARENT(i)Ai5 do exchange AiAPARENT(i)