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

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

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

3、的堆，稱(chēng)這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選”,13,38,27,49,76,65,49,97,13,輸出根并以最后一個(gè)元素代替之； 比較其左右孩子值的大小，并與其中較小者交換；,97,27,97,49,97,小根堆,堆調(diào)整與數(shù)組變化的關(guān)系,加入元素時(shí)向上調(diào)整 刪除元素時(shí)向下調(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-代碼見(jiàn)課本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.,你能畫(huà)出刪除堆頂元素時(shí)相應(yīng)數(shù)組的變化嗎？ 刪除元素代碼見(jiàn)課本204,一、堆和堆排序的概念 二、堆的調(diào)整 三、建堆 四、堆排序,7.5.2 堆和堆排序,第一種方法：,把一個(gè)數(shù)組看成兩部分，左邊是堆，右邊是還沒(méi)加入堆的元素，步驟如下： 1、數(shù)組里的第一個(gè)元素自然地是一個(gè)堆 2、然后從第二個(gè)元素開(kāi)始，一個(gè)個(gè)地加入左邊的堆，當(dāng)然，每加入一個(gè)元素就破壞了左邊元素堆的性質(zhì)，得重新把它調(diào)整為堆,創(chuàng)建堆,時(shí)間復(fù)雜度,該方法創(chuàng)建堆的時(shí)間復(fù)雜度為O

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

9、65，97，76，13，27，49的一組記錄，將其按關(guān)鍵字調(diào)整為一個(gè)小根堆。,49,38,65,97,76,13,27,49,首先， 調(diào)整從第n/2個(gè)元素開(kāi)始 將以該元素為根的二叉樹(shù)調(diào)整為堆 然后，將以序號(hào)為n/21的結(jié)點(diǎn)為根的二叉樹(shù)調(diào)整為堆； 再將以序號(hào)為n/22的結(jié)點(diǎn)為根的二叉樹(shù)調(diào)整為堆； 再將以序號(hào)為n/23的結(jié)點(diǎn)為根的二叉樹(shù)調(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頁(yè),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,時(shí)間復(fù)雜度分析,該方法創(chuàng)建堆的時(shí)間復(fù)雜度為O(