第八章堆積(已修改)
2025-10-22 12:12 本頁(yè)面
【正文】 第八章 堆 積 ? 堆積 （ heap）是樹結(jié)構(gòu)的第三種型態(tài)。堆積是一棵二元樹，其左右子樹節(jié)點(diǎn)的值均較其父母節(jié)點(diǎn)的值小。堆積的根節(jié)點(diǎn)值保證是該樹最大值。這中堆績(jī)稱為最大堆績(jī)。堆積的子樹可擺在左邊當(dāng)左子樹，也可擺在右邊當(dāng)右子樹，因此左右子樹俱有相同的性質(zhì)。 ? 堆積還有一個(gè)有趣的特性，就是以陣列實(shí)作較以連結(jié)串列實(shí)作佳。當(dāng)以陣列實(shí)作堆積時(shí)，已知父母節(jié)點(diǎn)的 註標(biāo)（ subscript）就可算出其左右子樹節(jié)點(diǎn)的註標(biāo)，反之亦然。 ? 若父母節(jié)點(diǎn)的 註標(biāo) i 從 0 開(kāi)始 計(jì)數(shù)時(shí)，則左子樹節(jié)點(diǎn)的註標(biāo)為 2*i+1，右子樹節(jié)點(diǎn)的註標(biāo)為 2*i+2。 ? 若父母節(jié)點(diǎn)的 註標(biāo) i 從 1 開(kāi)始 計(jì)數(shù)時(shí)，則左子樹節(jié)點(diǎn)的註標(biāo)為 2*i，右子樹節(jié)點(diǎn)的註標(biāo)為 2*i+1。 ? 已知子女節(jié)點(diǎn)的註標(biāo)也可算出其父母節(jié)點(diǎn)的註標(biāo)，因此處理的效率相當(dāng)高。 基本觀念 ? 一棵堆積是一棵二元樹，俱備下列的特性： ? 1. 這棵樹是一棵完整或接近完整的二元樹。 ? 2. 每一節(jié)點(diǎn)的鍵值大於或等於其子樹節(jié)點(diǎn)鍵值。 ? 一棵完整的二元樹是每一層次（ level）都佔(zhàn)滿，一棵接近完整的二元樹指其葉節(jié)點(diǎn)相差在一個(gè)層次以內(nèi)。堆積如下圖所示。 三種堆積舉例 ? 在上圖的兄弟節(jié)點(diǎn)裡，左節(jié)點(diǎn)有大於右節(jié)點(diǎn)者（ 139），左節(jié)點(diǎn)有小於右節(jié)點(diǎn)者（ 711， 1924），這對(duì)於前面章節(jié)說(shuō)明過(guò)的二元搜尋樹是不允許的。注意上圖（ c）是一棵接近完整的二元樹，第二層次是從左而右填滿的，這也是堆積的要求。 堆積有兩個(gè)基本的操作 ? 對(duì)於堆積有兩個(gè)基本的操作： 插入一個(gè)節(jié)點(diǎn) 以及 移除一個(gè)節(jié)點(diǎn) 。雖然堆積是一棵樹，但對(duì)它執(zhí)行遍訪、搜尋、列印的操作並無(wú)意義。要實(shí)作堆積的插入及移除節(jié)點(diǎn)操作，我們需要兩個(gè)演算法， 再堆上 （ reheap up）以及 再堆下 （ reheap down）。 再堆上作業(yè) ? 假想我們有一個(gè) N 個(gè)元素的接近完整二元樹，其前面的 N1 個(gè)元素均已滿足堆積的要求，但最後一個(gè)元素 N 卻不滿足堆積，換句話說(shuō)只要第 N 個(gè)元素滿足堆積的要求，整個(gè)結(jié)構(gòu)就是一個(gè)堆積了。再堆上作業(yè)將第 N 個(gè)元素往上堆，定位於正確的位置，使整個(gè)結(jié)構(gòu)成為一個(gè)堆積。 26往上移動(dòng) ? 上圖新元素 26 插入原來(lái)已成堆積的樹。最後的元素規(guī)定要擺在最右邊的。 26 比它的父母節(jié)點(diǎn) 13 還大，違反堆積的規(guī)定，必須互換，因此就往上移動(dòng)，如下圖所示。 26再往上移動(dòng) ? 26 比它的父母節(jié)點(diǎn) 43 還小，就不必再移動(dòng)，已經(jīng)定到正確的位置了。這種再堆上使成堆積的作業(yè)稱為再堆上操作。 再堆下作業(yè) ? 再堆下作業(yè)事實(shí)上是再堆上的相反操作。舉例如下圖。 堆積實(shí)作 ? 雖然堆積可以透過(guò)動(dòng)態(tài)樹結(jié)構(gòu)建立起來(lái)，但最常見(jiàn)的還是以陣列實(shí)作為宜。一個(gè)節(jié)點(diǎn)與其子女節(jié)點(diǎn)的關(guān)係可以計(jì)算出來(lái)，如下所述： ? 1. 若節(jié)點(diǎn)註標(biāo)為 i（從 0算起），則其子女節(jié)點(diǎn)的註標(biāo)計(jì)算 ? 如下： ? a). 左子女節(jié)點(diǎn)註標(biāo)為 2*i+1 ? b). 右子女節(jié)點(diǎn)註標(biāo)為 2*i+2 ? 2. 若節(jié)點(diǎn)註標(biāo)為 i（從 0算起），則其父母節(jié)點(diǎn)的註標(biāo)計(jì)算 ? 如下： 取 (i1)/2 之整數(shù)部份 。 ? 3. 左子女節(jié)點(diǎn)註標(biāo)為 j，右子女節(jié)點(diǎn)註標(biāo)為 j+1。 ? 右子女節(jié)點(diǎn)註標(biāo)為 k，左子女節(jié)點(diǎn)註標(biāo)為 k1。 ? 4. 設(shè)完整堆積元素?cái)?shù)為 n，第一個(gè)葉節(jié)點(diǎn)為 (n/2) 之整數(shù)部份。最後的枝節(jié)點(diǎn)註標(biāo)為 (n/2)1 之整數(shù)部份。 堆積以樹及陣列表示 ? 1. 33 的註標(biāo)為 2（從 0算起），左子女節(jié)點(diǎn) 24 註標(biāo) 為 2*2+1=5，右子女節(jié)點(diǎn) 20 註標(biāo)為 2*2+2=6。 ? 2. 9 的註標(biāo)為 4（從 0算起），其父母節(jié)點(diǎn) 57 的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1