算法导论CN2nd第六章堆排序6寸kindle版

《算法导论CN2nd第六章堆排序6寸kindle版》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章堆排序本章要介绍另一种排序算法，即堆排序（heapsort）。像合并排序而不像插入顺序，堆排序的运行时间为Onn(lg)。像插入排序而不像合并排序，它是一种原地（inplace）排序算法：在任何时候，数组中只有常数个元素存储在输入数组以外。这样，堆排序就把我们讨论过的两种排序算法的优点结合起来。堆排序还引入另一种算法设计技术：利用某种数据结构（在此算法中为“堆”）来管理算法执行中的信息。堆数据结构不只是在堆排序中有用，还可以构成一个有效的优先队列。堆数据结构在后续章节的算法中还将重复出现。“堆”这个词最初是在堆排序中提出

2、的，但后来就逐渐指“废料收集存储区”，就像程序设计语言Lisp和Java中所提供的设施那样。我们这里的堆数据结构不是废料收集存储区；本书中以后任何地方提到堆结构，都是指本章定义的结构。6.1堆（二叉）堆数据结构是一种数组对象，如图6-1所示，它可以被视为一棵完全二叉树（见B.5.3节）。树中每个结点与数组中存放该结点值的那个元素对应。树的每一层都是填满的，最后一层可能除外（最后一层从一个结点的左子树开始填）。表示堆的数组A是—个具有两个属性的对象；A.length是数组中的元素个数，A.heap-size是存放在A中的堆的元素

3、个数。就是说，虽然从A[1..A.length]中都可以包含有效值，但A[A.heap-size]之后的元素都不属于相应的堆，此处A.heapsize−≤A.length。树的根为A[1]，给定了某个结点的下标i，其父结点PARENT（i）、左儿子LEFT（i）和右儿子RIGHT（i）的下标可以简单地计算出来：PARENT(i)1return⎢⎣i/2⎥⎦LEFT(i)1return2iRIGHT(i)1return2i+1图6-1一个最大堆（大根堆）可被看作a）一棵二叉树和b）—个数组。圆圈中的数字表示树中每个结点存储的值，

4、结点上方的数宇表示对应的数组下标。数组上下的连线表示父子关系，且父结点总在子结点的左边，这棵树的高度为3；存储值为8的4号结点的高度为1。在大多数计算机上，LEFT过程可以在一条指令内计算出2i，方法是将i的二进制表示左移1位。类似地，RIGHT过程也可以通过将i的二进制表示左移1位并在低位中加1，快速计算出2i+1，PARENT过程则可以通过把i右移1位而得到⎢⎥⎣⎦i/2。在一个好的堆排序的实现中，这二个过程通常是用“宏”过程或是“内联”过程实现的。二叉堆有两种：最大堆和最小堆（小根堆）。在这两种堆中，结点内的数值都要满足

5、堆特性，其细节则视堆的种类而定。在最大堆中，最大堆特性是指除了根以外的每个结点i，有A[PARENT(i)]≥A[i]即某个结点的值至多是和其父结点的值一样大。这样，堆中的最大元素就存放在根结点中；并且，在以某一个结点为根的子树中，各结点的值都不大于该子树根结点的值。最小堆的组织方式则刚好相反；最小堆特性是指除了根以外的每个结点i，有A[PARENT(i)]≤A[i]最小堆的最小元素是在根部。在堆排序算法中，我们使用的是最大堆，最小堆通常在构造优先队列时使用，具体将在6.5节中讨论。对于某个特定的应用，我们将确切地指明需要的是

6、最大堆还是最小堆。当某一性质既适合于最大堆也适合于最小堆时，我们就只使用“堆”这个词。堆可以被看成是一棵树，结点在堆中的髙度定义为从本结点到叶子的最长简单下降路径上边的数目；定义堆的高度为树根的高度。因为具有n个元素的堆是基于一棵完全二叉树的，因而其高度为Θ(lg)n（见练习6.1-2）。我们将看到，堆结构上的一些基本操作的运行时间至多与树的高度成正比，为On(lg)。本章的下面部分将给出五个基本过程，并说明它们在排序算法和优先级队列数据结构中如何使用。MAX-HEAPIFY过程，其运行时间为On(lg)，是保持最大堆性质的关

7、键。BUILD-MAX-HEAP过程，以线性时间运行，可以在无序的输入数组基础上构造出最大堆。HEAPSORT过程，运行时间为Onn(lg)，对一个数组原地进行排序。MAX-HEAP-INSERT，HEAP-EXTRACT-MAX，HEAP-INCREASE-KEY和HEAP-MAXIMUM过程的运行时间为On(lg)，可以让堆结构作为优先队列使用。6.2保持堆的性质MAX-HEAPIFY是对最大堆进行操作的重要的子程序，其输入为一个数组A和下标i。当MAX-HEAPIFY被调用时，我们假定以LEFT（i）和RIGHT（i）为

8、根的两棵二叉树都是最大堆，但这时A[i]可能小于其子女，这样就违反了最大堆性质。MAX-HEAPIFY让A[i]在最大堆中“下降”，使以i为根的子树成为最大堆。MAX-HEAPIFY(,)Ai1Lli=EFT()2Rri=IGHT()3.ifl≤>AheapsizeandAl