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