堆和堆排序092312113林秋照

1、堆和堆排序主讲人：林秋照堆的定义堆可以定义为一颗二叉树，树的节点中包含键（每个节点一个键），并且满足两个条件：1、树的形状要求这棵二叉树是基本完备的（或者简称为完全二叉树），这意味着，树的每一层都是满的，除了最后一层最右边的元素有可能缺位。2、父母优势要求每一个节点的键都要大于或等于它的子女的键（对于任何叶子我们认为这个条件都是自动满足的）。3rir2i r2i+1 1236276549817355403498例如:是堆14不4例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）堆序列是完全二叉树，则堆序列是完全二叉树，则堆顶元素（完全二叉堆顶元素（完

2、全二叉树的根）必为序列中树的根）必为序列中n个元素的最小值或最大个元素的最小值或最大值值如下图，是一个堆和数组的相互关系：二叉堆一般分为两种：最大堆和最小堆。两种堆内部的数据都要满足自己的特点。比如最大堆的特点是，每个父节点的元素值都不小于其孩子结点（如果存在）的元素值，因此，最大堆的最大元素值出现在根结点（堆顶）最小堆的性质与最大堆恰好相反。堆的重要特性1、只存在一棵N个节点的完全二叉树。它的高度等于堆的根总是包含了堆得最大元素。3、堆的一个节点以及该节点的子孙也是一个堆。4、可以用数组来实现堆，方法是用从上向下、从左向右的方式来记录堆的元素。可以在这种数组从1到N的位置上存放堆元素，留下H

3、0，要么让它空着，要么在其中放一个限位器，它的值大于堆中的任何一个元素。堆的构造堆的构造主要有两种方法。第一种是自底向上堆构造。在初始化一棵包含N个节点的完全二叉树时，我们就按照给定的顺序来放置键；然后按照下面的方法对树进行“堆化”。从最后的父母节点开始到根为止，该算法检查这些节点的键是否满足父母优势要求。如果该节点不满足，该算法把节点的键K和它子女的最大键进行交换，然后再检查在新位置上，K是不是满足父母优势要求。这个过程一直持续到，对K的父母优势要求满足为止（最终它必须满足，因为对于每个叶子中的键来说，这个条件是自动满足的）。对于以当前父母节点为根的子树，在完成它的“堆化”以后，该算法对于该

4、节点的直接前趋进行同样的操作。在对树的根完成了这种操作以后，该算法就停止了。8建堆是一个从下往上进行“筛选”的过程。40554973816436122798例如: 原始序列为（40,55,49,73,12,27,78,81,64,36）123681734998817355l左/右子树都已经调整为堆l最后只要调整根结点，使整个二叉树是个“堆”即可。9849406436122799881497355641236274012输出98（ 98 和 12 进行互换）之后，它就不是堆了需要对它进行“筛选”98128173641298比较比较大顶堆大顶堆调节过程：调节过程：大顶堆的排序结果是升序排序大顶堆的

5、排序结果是升序排序另一种算法（效率较低）通过把新的键连续插入预先构造好的堆，来构造一个新堆。首先，把一个包含键K的新节点附加在当前堆得最后一个叶子后面。然后按照下面的方法把K筛选到他的适当位置。拿K和它父母的键做比较：如果后者大于等于K，算法停止（该机=结构已经是一个堆了）；否则，交换这两个键并把K和它的新父母做比较。这种交换一直持续到K不大于它的最后一个字母，或者是达到了树的根为止（图6.12是一个图示）。在这个算法中，我们也可以把一个空节点向上筛选，直到达到合适的位置，才把K的值赋给它。11例：小顶堆13273849657650979727384965765013输出：1327493897

6、65765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 38124965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 65137665972738495013输出：

7、13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97算法HEAPBOTTOMUP/用自底向上算法，从给定数组的元素中构造一个堆/输入：一个可排序元素的数组H.R1N/输出：一个堆H.R1N VOID HEAPADJUST (HEAPTYPE &H, INT S, INT M) / 已知H.RS.M中记录的关键字除H.RS.KEY之外均满足堆的定义，本函数依据 / 关键字的大小对H.RS进行调整，使H.RS.M成为一个大顶堆(对其中记录的关键字而

8、言) RC = H.RS; / 暂存根结点的记录 FOR ( J=2*S; J=M; J*=2 ) / 沿KEY较大的孩子结点向下筛选 IF ( JM & H.RJ.KEY= H.RJ.KEY ) BREAK; / 不需要调整 H.RS = H.RJ; S = J; / 把大关键字记录往上调 H.RS = RC; / 回移筛选下来的记录 / HEAPADJUST从堆中删除最大的键第一步：根的键和堆的最后一个键K做交换。第二步：堆的规模减1。第三步：严格按照我们在自底向上堆构造算法中的做法，把K沿着树向下筛选，来对这棵树较小的树进行“堆化”。也就是说，验证K是否满足父母优势：如果它满足，

9、我们就完成了；如果不满足，K和它较大的子女做交换；然后重复这个操作，知道K在新位置中满足了父母优势要求为止。删除的效率取决于在交换和堆的规模减1后，树的“堆化”所需的键值比较次数。既然它所需的键值比较次数不可能超过堆的高度的两倍，删除的时间效率也是属于O（的。堆排序堆排序的过程对N个数据的原始无序序列建堆，输出堆顶元素将剩下的N-1个元素调整为堆，输出堆顶元素将剩下的N-2个元素调整为堆，输出堆顶元素.剩下的最后一个元素，本身就是堆堆排序算法VOID HEAPSORT ( HEAPTYPE &H ) CREATEHEAP(H); /建立初始堆 H.R1H.RN; /堆顶元素与最后一个元

10、素交换 FOR(I=N-1; I1; I-) /连续进行堆调节和交换 HEAPADJUST(H); H.R1H.RI; VOID HEAPSORT ( HEAPTYPE &H ) / 对顺序表H进行堆排序。 FOR ( I=H.LENGTH/2; I0; -I ) / 把H.R1.H.LENGTH建成大顶堆 HEAPADJUST ( H, I, H.LENGTH ); W=H.R1 ; H.R1= H.RH.LENGTH; H.RH.LENGTH=W; /交换堆顶和堆底的记录 FOR ( I=H.LENGTH-1; I1; -I ) HEAPADJUST(H, 1, I); / 从根开始调整，将H 重新调整为大顶堆 W=H.R1; H.R1=H.RI; H.RI=W; / 相互交换 堆排序的时