堆与堆排序

《堆与堆排序》由会员分享，可在线阅读，更多相关《堆与堆排序（47页珍藏版）》请在金锄头文库上搜索。

1、堆与堆排序,软件学院 王建文, 一、堆和堆排序的概念 二、堆的调整 三、建堆 四、堆排序,7.5.2 堆和堆排序,堆的定义： 若n个元素的序列a1 a2 an 满足 ai a2i 或 ai a2i ai a2i+1 ai a2i+1 则分别称该序列a1 a2 an为小根堆 和大根堆。 从堆的定义可以看出，堆实质是满足如下性质的完全二叉树： 二叉树中任一非叶子结点均小于(大于)它的孩子结点,例: 下面序列为堆，对应的完全二叉树分别为:,77 35 62 55 14 35 48 14 48 35 62 55 98 35 77,堆的应用-优先级队列,服务排队-见课本200, 例5.1 堆排序,堆排序

2、 若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）如此反复，便能得到一个有序序列，这个过程称之为堆排序。,实现堆排序需解决两个问题： 1、如何由一个无序序列建成一个堆？ 2、如何在输出堆顶元素后，调整剩余元素为一个新的堆？ 下面先讨论第二个问题：,一、堆和堆排序的概念 二、堆的调整 三、建堆 四、堆排序,7.5.2 堆和堆排序,如何在输出堆顶元素后，调整剩余元素为一个新的堆？ 解决方法： 输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新

3、的堆，称这个从堆顶至叶子的调整过程为“筛选”,13,38,27,49,76,65,49,97,13,输出根并以最后一个元素代替之； 比较其左右孩子值的大小，并与其中较小者交换；,97,27,97,49,97,小根堆,堆调整与数组变化的关系,加入元素时向上调整 删除元素时向下调整,加入元素,Fig. 27-2 The steps in adding 85 to the maxheap of Figure 27-1a,Adding an Entry,Begin at next available position for a leaf Follow path from this leaf towa

4、rd root until find correct position for new entry As this is done Move entries from parent to child Makes room for new entry,Adding an Entry,Fig. 27-3 A revision of steps shown in Fig. 27-2 to avoid swaps.,Adding an Entry,Fig. 27-4 An array representation of the steps in Fig. 27-3 continued ,Adding

5、an Entry,Fig. 27-4 (ctd.) An array representation of the steps in Fig. 27-3.,Adding an Entry-代码见课本203,Algorithm for adding new entry to a heap,Algorithm add(newEntry) if (the array heap is full) Double the size of the array newIndex = index of next available array location parentIndex = newIndex/2 /

6、 index of parent of available location while (newEntry heapparentIndex) heapnewIndex = heapparentIndex / move parent to available location / update indices newIndex = parentIndex parentIndex = newIndex/2 / end while,删除元素,Fig. 27-5 The steps to remove the entry in the root of the maxheap of Fig. 27-3

7、d,Removing the Root,Fig. 27-6 The steps that transform a semiheap into a heap without swaps.,你能画出删除堆顶元素时相应数组的变化吗？ 删除元素代码见课本204,一、堆和堆排序的概念 二、堆的调整 三、建堆 四、堆排序,7.5.2 堆和堆排序,第一种方法：,把一个数组看成两部分，左边是堆，右边是还没加入堆的元素，步骤如下： 1、数组里的第一个元素自然地是一个堆 2、然后从第二个元素开始，一个个地加入左边的堆，当然，每加入一个元素就破坏了左边元素堆的性质，得重新把它调整为堆,创建堆,时间复杂度,该方法创建

8、堆的时间复杂度为O (n log n),可以看出： 对一个无序序列反复“筛选”就可以得到一个堆 即：从一个无序序列建堆的过程就是一个反复“筛选”的过程。 那么：怎样判断一个序列是一个堆？或者说，建堆操作从哪儿着手？,第二种方法：自底向上创建堆,显然： 单结点的二叉树是堆；在完全二叉树中所有以叶子结点（序号i n/2）为根的子树是堆。 这样，我们只需依次将以序号为n/2，n/21，, 1的结点为根的子树均调整为堆即可。 即：对应由n个元素组成的无序序列，“筛选”只需从第n/2个元素开始。,由于堆实质上是一个完全二叉树，那么我们可以顺序存储一个堆。 下面以一个实例介绍建一个小根堆的过程。 例：有关

9、键字为49，38，65，97，76，13，27，49的一组记录，将其按关键字调整为一个小根堆。,49,38,65,97,76,13,27,49,首先， 调整从第n/2个元素开始 将以该元素为根的二叉树调整为堆 然后，将以序号为n/21的结点为根的二叉树调整为堆； 再将以序号为n/22的结点为根的二叉树调整为堆； 再将以序号为n/23的结点为根的二叉树调整为堆；,49,65,97,76,13,49,38,27,97,49,97,49,65,13,65,13,49,49,13,13,27,49,27,49,筛选过程的算法描述为： sift (rectype R , int i , int m )

10、/ 在数组R中将下标从i到m的元素序列调整为堆，即将以Ri为根的子树调整为堆；初次调整的是以序号m/2的结点为根的子树； int j ; j = 2*i ; while ( j Rj+1.key) j + ; / 比较左右孩子的大小，使j为较小的孩子的下标,if ( Ri.key Rj.key ) Ri Rj ; / 将较小的孩子与根交换 i = j ; j = 2*i ; / 上述交换可能使以该孩子结点为根的子树不再为堆，则需重新调整 else break ; ,将初始无序的R1到Rn建成一个小根堆，可用以下语句实现： for ( i = n/2 ; i = 1 ; i - - ) sift

11、 ( R , i , n ) ;,自底向上地创建堆,15,16,12,4,7,6,20,23,25,15,16,5,12,4,11,7,6,27,20,23,Example (contd.),25,15,16,5,12,4,11,9,6,27,20,23,15,25,16,4,12,5,6,9,11,23,20,27,Example (contd.),7,15,25,16,4,12,5,8,6,9,11,23,20,27,4,15,25,16,5,12,7,6,8,9,11,23,20,27,Example (end),4,15,25,16,5,12,7,10,6,8,9,11,23,20,2

12、7,5,15,25,16,7,12,10,4,6,8,9,11,23,20,27,Analysis,We visualize the worst-case time of a downheap with a proxy path that goes first right and then repeatedly goes left until the bottom of the heap (this path may differ from the actual downheap path) Since each node is traversed by at most two proxy p

13、aths, the total number of nodes of the proxy paths is O(n) Thus, bottom-up heap construction runs in O(n) time Bottom-up heap construction is faster than n successive insertions and speeds up the first phase of heap-sort,时间复杂度分析,该方法创建堆的时间复杂度为O( n ) 证明过程请看教材341页,一、堆和堆排序的概念 二、堆的调整 三、建堆 四、堆排序,7.5.2 堆和堆

14、排序,Heapsort,Fig. 27-9 A trace of heapsort (a c),Heapsort,Fig. 27-9 A trace of heapsort (d f),Heapsort,Fig. 27-9 A trace of heapsort (g i),Heapsort,Fig. 27-9 A trace of heapsort (j l),由以上分析知： 若对一个无序序列建堆，然后输出根；重复该过程就可以由一个无需序列输出有序序列。 实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。,堆排序算法如下： HeapSort ( rectype R )

15、 /对R1到Rn进行堆排序 int i ; rectype temp ; for ( i = n/2 ; i = 1 ; i - - ) sift ( R , i , n ) ; /建初始堆 for ( i = n ; i 1 ; i - - ) /进行n1趟排序 temp=R1; R1=Ri; Ri=temp; /根与最后一个元素交换 sift ( R, 1, i -1) /对R1到Ri -1重新建堆 ,堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。 堆排序在最坏情况下，其时间复杂度也为O(nlog2n)， 这是堆排序的最大优点。 另外，堆排序仅需一个记录大小供交换用的辅助存储空间。 然而堆排序是一种不稳定的排序方法， 它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。,Heapsort,public static void heapSort(Comparable array, int n) / create first heap for (int index = n/2; index = 0; index-) reheap(array, index, n-1); swap(array, 0, n-