第八章堆积-wenkub
2022-10-22 12:12:13 本页面
【正文】 *1+2=4 個位置，其值為 13。 • struct heapTag *heap。若 size 成員值已達 0 值則傳回 0 值。 • } 從堆積移除節點 • 從堆積 heap 裡移除資料 *dataptr 所指的節點，該指標為資料陣列第零個元素的位址，即 heapdata[0]，它是堆積裡最大值者，然後將最後的元素移到陣列第零個元素的位址，進行 ReheapDown() 再堆下作業，使滿足堆積的要求。 • (heaplast)。 • } • } • return。 • if (heappare(data[child],data[parent])0) • { • temp=data[parent]。 • } 插入堆積 • void ReheapUp(struct heapTag *heap, int child) • { • int parent。 • ++(heapsize)。 • heapdata[heaplast] = dataptr。 • } 建立堆積結構 建立堆積結構 • 需要提供兩個引數， 第一個是最大容量之元素個數 maxsize， 第二個是比較的函式名稱 pare。 • heappare = pare。 • heap = malloc(sizeof(struct heapTag))。 • }。 • int last。 • 2. 9 的註標為 4（從 0算起），其父母節點 57 的註標 為 (41)/2 整數部份為 1。 • 右子女節點註標為 k，左子女節點註標為 k1。舉例如下圖。 26 比它的父母節點 13 還大，違反堆積的規定，必須互換，因此就往上移動，如下圖所示。 再堆上作業 • 假想我們有一個 N 個元素的接近完整二元樹，其前面的 N1 個元素均已滿足堆積的要求，但最後一個元素 N 卻不滿足堆積，換句話說只要第 N 個元素滿足堆積的要求，整個結構就是一個堆積了。注意上圖（ c）是一棵接近完整的二元樹，第二層次是從左而右填滿的，這也是堆積的要求。 • 2. 每一節點的鍵值大於或等於其子樹節點鍵值。 • 若父母節點的 註標 i 從 0 開始 計數時，則左子樹節點的註標為 2*i+1，右子樹節點的註標為 2*i+2。這中堆績稱為最大堆績。第八章 堆 積 • 堆積 （ heap）是樹結構的第三種型態。堆積的子樹可擺在左邊當左子樹，也可擺在右邊當右子樹，因此左右子樹俱有相同的性質。 • 若父母節點的 註標 i 從 1 開始 計數時，則左子樹節點的註標為 2*i，右子樹節點的註標為 2*i+1。 • 一棵完整的二元樹是每一層次（ level）都佔滿，一棵接近完整的二元樹指其葉節點相差在一個層次以內。 堆積有兩個基本的操作 • 對於堆積有兩個基本的操作： 插入一個節點 以及 移除一個節點 。再堆上作業將第 N 個元素往上堆，定位於正確的位置，使整個結構成為一個堆積。 26再往上移動 • 26 比
教学课件相关推荐
鄂ICP备17016276号-1