1、最大堆的定義及其常用操作：

1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define true 1 5 #define false 0 6 #define ERROR -1 7 typedef int ElementType; 8 typedef int bool; 9 10 typedef struct HNode *Heap; /* 堆的類型定義 */ 11 struct HNode 12 { 13 ElementType *Data; /* 存儲元素的數組 */ 14 int Size; /* 堆中當前元素的個數 */ 15 int Capacity; /* 堆的最大容量 */ 16 }; 17 18 typedef Heap MaxHeap; /* 堆的最大容量 */ 19 20 MaxHeap CreatHeap(int MaxSize); /* 創建空的最大堆，其最大長度為MaxSize */ 21 bool IsEmpty(MaxHeap H); /* 判斷最大堆是否為空 */ 22 bool IsFull(MaxHeap H); /* 判斷最大堆是否已滿 */ 23 bool Insert(MaxHeap H, ElementType X); /* 插入成功返回true，否則返回false */ 24 ElementType DeleteMax(MaxHeap H); /* 刪除并返回H中最大的元素 */

?

2、函數實現：

1 MaxHeap CreatHeap(int MaxSize) 2 { 3 MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode)); 4 H->Data = (ElementType *)malloc((MaxSize+1) * sizeof(ElementType)); /* 數組起始單元為1，下標0沒有存在堆中，是無用的，所以應該分配MaxSize+1個元素 */ 5 H->Size = 0; 6 H->Capacity = MaxSize; 7 8 return H; 9 } 10 11 bool IsEmpty(MaxHeap H) 12 { 13 return H->Size == 0; 14 } 15 16 bool IsFull(MaxHeap H) 17 { 18 return H->Size == H->Capacity; 19 } 20 21 bool Insert(MaxHeap H, ElementType X) 22 { 23 if(IsFull(H)) 24 { 25 printf("堆已滿，插入失敗！"); 26 return false; 27 } 28 29 ++H->Size; 30 int i = H->Size; /* i指向插入后堆中的最后一個元素的位置 */ 31 32 while(H->Data[i/2] < X && i > 1) /*元素是從下標1開始存儲的，所以i必須大于1 */ 33 { 34 H->Data[i] = H->Data[i/2]; /* 上濾X */ 35 i = i/2; 36 } 37 H->Data[i] = X; /* 將X插入到正確的位置 */ 38 return true; 39 40 } 41 42 ElementType DeleteMax(MaxHeap H) /* 刪除并返回H中最大的元素 */ 43 { 44 if(IsEmpty(H)) 45 { 46 printf("堆為空，刪除失敗！"); 47 return ERROR; 48 } 49 ElementType MaxItem, X; 50 MaxItem = H->Data[1]; 51 X = H->Data[H->Size]; /* 取出刪除前堆的最后一個元素 */ 52 --H->Size; 53 54 int Parent, Child; 55 for(Parent = 1; Parent*2 <= H->Size; Parent = Child) /* 如果有兒子 */ 56 { 57 Child = Parent * 2; 58 if(Child != H->Size && H->Data[Child] < H->Data[Child+1]) /* 有右兒子, 且左兒子小于右兒子 */ 59 ++Child; /* Child指向左右子節點的較大者 */ 60 if(H->Data[Child] > X) 61 H->Data[Parent] = H->Data[Child]; /* 下濾X */ 62 else 63 break; /* 子節點都比X小，則找到了X的插入位置，跳出循環 */ 64 65 } 66 H->Data[Parent] = X; 67 68 return MaxItem; 69 }

?

?

3、最大堆的建立

目的：將已經存在的N個元素按照最大堆的要求存放在一個一維數組中。

?

方法1：通過插入操作，將N個元素一個個相繼插入到一個初始為空的堆中去，其時間代價最大為O(NlogN)。

方法2：在線性時間復雜度O(N)下建立最大堆。

　 (1) 將N個元素按輸入順序存入，先滿足完全二叉樹的結構特性

　 (2) 調整個節點位置，以滿足最大堆的有序特性

?

方法2的時間復雜度分析：

從一個無序的完全二叉樹進行節點向下過濾操作是構建最大堆的主要工作。某一節點向下過濾要與其下層的子孫節點比較鍵值，

因此最大的比較次數是樹中各節點高度的和，這個高度和也就決定了算法的復雜度。而關于各節點的高度，我們有如下結論：

　　一個高度為h的完全二叉樹最多包含2^h - 1個節點(完美二叉樹) ， 這些節點的高度和為 2^h - 1 - h。 ( 證明過程見《數據結構與算法分析-C語言描述》P141.)

又由于一個完全二叉樹的節點個數N是在2^(h-1) 和 2^h - 1之間，因此節點的高度和為O(N)，說明最大堆建立算法的復雜度與節點個數呈線性關系。

?

用方法2構建最大堆的代碼實現：

?

1 void PercDown(MaxHeap H, int p) 2 { /* 下濾：將H中以H->Data[p]為根的子堆調整為最大堆 */ 3 int Parent, Child; 4 ElementType X; 5 6 X = H->Data[p]; /* 取出根節點存放的值 */ 7 8 for(Parent = p; Parent*2 <= H->Size; Parent = Child) /* 如果有兒子 */ 9 { 10 Child = Parent * 2; 11 if(Child != H->Size && H->Data[Child] < H->Data[Child+1]) /* 有右兒子, 且左兒子小于右兒子 */ 12 ++Child; /* Child指向左右子節點的較大者 */ 13 if(H->Data[Child] > X) 14 H->Data[Parent] = H->Data[Child]; /* 下濾X */ 15 else 16 break; /* 子節點都比X小，則找到了X的插入位置，跳出循環 */ 17 18 } 19 H->Data[Parent] = X; 20 } 21 22 void BuildHeap(MaxHeap H) 23 { /* 調整H->Data[]中的元素，使滿足最大堆的有序性 */ 24 /* 這里假設所有H->Size個元素都已經存在H->Data[]中 */ 25 26 int i; 27 28 /* 從最后一個節點的父節點開始，到根節點1，逐個調節子樹 */ 29 for(i = H->Size/2; i > 0; --i) 30 PercDown(H, i); 31 32 }

?

由于PercDown函數中的參數MaxHeap都必須是最大堆，所以BuildHeap必須從最后一個節點的父節點開始，逐漸把子樹全部調整為最大堆。

轉載于:https://www.cnblogs.com/FengZeng666/p/9785626.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的最大堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。