數(shù)據(jù)結(jié)構(gòu)_課件_堆與堆排序.ppt

1、堆與堆排序,軟件學(xué)院 王建文, 一、堆和堆排序的概念 二、堆的調(diào)整 三、建堆 四、堆排序,7.5.2 堆和堆排序,堆的定義： 若n個元素的序列a1 a2 an 滿足 ai a2i 或 ai a2i ai a2i+1 ai a2i+1 則分別稱該序列a1 a2 an為小根堆 和大根堆。 從堆的定義可以看出，堆實(shí)質(zhì)是滿足如下性質(zhì)的完全二叉樹： 二叉樹中任一非葉子結(jié)點(diǎn)均小于(大于)它的孩子結(jié)點(diǎn),例: 下面序列為堆，對應(yīng)的完全二叉樹分別為:,77 35 62 55 14 35 48 14 48 35 62 55 98 35 77,堆的應(yīng)用-優(yōu)先級隊(duì)列,服務(wù)排隊(duì)-見課本200, 例5.1 堆排序,堆排序

2、 若在輸出堆頂?shù)淖钚≈担ㄗ畲笾担┖?，使得剩余n-1個元素的序列重又建成一個堆，則得到n個元素的次小值（次大值）如此反復(fù)，便能得到一個有序序列，這個過程稱之為堆排序。,實(shí)現(xiàn)堆排序需解決兩個問題： 1、如何由一個無序序列建成一個堆？ 2、如何在輸出堆頂元素后，調(diào)整剩余元素為一個新的堆？ 下面先討論第二個問題：,一、堆和堆排序的概念 二、堆的調(diào)整 三、建堆 四、堆排序,7.5.2 堆和堆排序,如何在輸出堆頂元素后，調(diào)整剩余元素為一個新的堆？ 解決方法： 輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新

3、的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”,13,38,27,49,76,65,49,97,13,輸出根并以最后一個元素代替之； 比較其左右孩子值的大小，并與其中較小者交換；,97,27,97,49,97,小根堆,堆調(diào)整與數(shù)組變化的關(guān)系,加入元素時向上調(diào)整 刪除元素時向下調(diào)整,加入元素,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 arraynewIndex = index of next available array locationparentIndex = newIndex/2 / ind

6、ex of parent of available locationwhile (newEntry heapparentIndex)heapnewIndex = heapparentIndex / move parent to available location/ update indicesnewIndex = parentIndexparentIndex = newIndex/2 / end while,刪除元素,Fig. 27-5 The steps to remove the entry in the root of the maxheap of Fig. 27-3d,Removin

7、g the Root,Fig. 27-6 The steps that transform a semiheap into a heap without swaps.,你能畫出刪除堆頂元素時相應(yīng)數(shù)組的變化嗎？ 刪除元素代碼見課本204,一、堆和堆排序的概念 二、堆的調(diào)整 三、建堆 四、堆排序,7.5.2 堆和堆排序,第一種方法：,把一個數(shù)組看成兩部分，左邊是堆，右邊是還沒加入堆的元素，步驟如下： 1、數(shù)組里的第一個元素自然地是一個堆 2、然后從第二個元素開始，一個個地加入左邊的堆，當(dāng)然，每加入一個元素就破壞了左邊元素堆的性質(zhì)，得重新把它調(diào)整為堆,創(chuàng)建堆,時間復(fù)雜度,該方法創(chuàng)建堆的時間復(fù)雜度為O

8、 (n log n),可以看出： 對一個無序序列反復(fù)“篩選”就可以得到一個堆 即：從一個無序序列建堆的過程就是一個反復(fù)“篩選”的過程。 那么：怎樣判斷一個序列是一個堆？或者說，建堆操作從哪兒著手？,第二種方法：自底向上創(chuàng)建堆,顯然： 單結(jié)點(diǎn)的二叉樹是堆；在完全二叉樹中所有以葉子結(jié)點(diǎn)（序號i n/2）為根的子樹是堆。 這樣，我們只需依次將以序號為n/2，n/21，, 1的結(jié)點(diǎn)為根的子樹均調(diào)整為堆即可。 即：對應(yīng)由n個元素組成的無序序列，“篩選”只需從第n/2個元素開始。,由于堆實(shí)質(zhì)上是一個完全二叉樹，那么我們可以順序存儲一個堆。 下面以一個實(shí)例介紹建一個小根堆的過程。 例：有關(guān)鍵字為49，38，

9、65，97，76，13，27，49的一組記錄，將其按關(guān)鍵字調(diào)整為一個小根堆。,49,38,65,97,76,13,27,49,首先， 調(diào)整從第n/2個元素開始 將以該元素為根的二叉樹調(diào)整為堆 然后，將以序號為n/21的結(jié)點(diǎn)為根的二叉樹調(diào)整為堆； 再將以序號為n/22的結(jié)點(diǎn)為根的二叉樹調(diào)整為堆； 再將以序號為n/23的結(jié)點(diǎn)為根的二叉樹調(diào)整為堆；,49,65,97,76,13,49,38,27,97,49,97,49,65,13,65,13,49,49,13,13,27,49,27,49,Heapsort,Fig. 27-9 A trace of heapsort (a c),Heapsort,F

10、ig. 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),堆排序算法實(shí)現(xiàn),課本290頁,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

11、 path may differ from the actual downheap path) Since each node is traversed by at most two proxy paths, 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,時間復(fù)雜度分析,該方法創(chuàng)建堆的時間復(fù)雜度為O(