1、基本概念
堆分為小根堆和大根堆，對於一個小根堆，它是具有如下特性的一棵完全二叉樹：
（1）若樹根結點存在左孩子或右孩子，則根結點的值（或某個域的值）小於等於左右孩子結點的值（或某個域的值）
（2）以左、右孩子為根的子樹又各是一個堆。
大根堆的定義將上面的小於等於改成大於等於即可。
根據根的定義，小根堆的堆頂結點具有最小值，大根堆的堆頂結點具有最大值。
我們以下將只對小根堆進行討論。
2、堆的存儲結構
由於堆是一棵完全二叉樹，所以適宜采用順序存儲結構，這樣能夠充分利用存儲空間。
順序存儲結構：
對堆中所有結點進行編號，作為下標存儲到指定數組的對應元素中，下標從0開始。按照從上到下，同一層從左到右進行。
設堆中有n個結點，則編號為 0 ~ n-1，則有如下性質：
（1）編號為 0 至 [n/2-1] 的結點為分支結點， 編號為 [n/2] 至 n-1 的結點為葉子結點；
（2）當 n 為奇數則每個分支結點既有左孩子又有右孩子，當 n 為偶數則每個分支結點只有左孩子沒有右孩子
（3）對於每個編號為 i 的分支結點，其左孩子結點的編號為 2i+1，右孩子結點的編號為 2i+2
（4）除編號為0的堆頂結點外，對於其余編號為 i 的結點，其雙親結點的編號為 [(i-1)/2]
下圖為一個堆及其順序存儲結構
<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPGg0PjOhorbRtcSy2df3vLDUy8vjPC9oND4KPHA+08PI58/Cs8zQ8s/qz7jVucq+ttG1xLLZ1/e8sNTLy+OjrLPM0PLWrrrzvau7ubvh09DP6s+4tcS9sr3istnX97n9s8y1xMq1z9bUrcDtoaM8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include
#include
typedef int ElemType;
struct HeapSq //定義堆的順序存儲類型
{
ElemType* heap; //定義指向動態數組空間的指針
int len; //定義保存堆長度的變量,即數組長度，數組下標從0開始
int MaxSize; //用於保存初始化時所給的動態數組空間的大小
};
//1、初始化堆
void InitHeap(struct HeapSq* HBT, int MS)
{
if (MS <= 0)
{
printf("數組長度參數不合適，需重新給定！\n");
exit(1);
}
HBT->heap = malloc(MS*sizeof(ElemType));
if (!HBT->heap)
{
printf("用於動態分配的內存空間用完，退出運行！\n");
exit(1);
}
HBT->MaxSize = MS;
HBT->len = 0;
}
//2、清除堆
void ClearHeap(struct HeapSq* HBT)
{
if (HBT->heap != NULL)
{
free(HBT->heap);
HBT->len = 0;
HBT->MaxSize = 0;
}
}
//3、檢查一個堆是否為空
int EmptyHeap(struct HeapSq* HBT)
{
if (HBT->len == 0)
return 1;
else
return 0;
}
//4、向堆中插入一個元素
void InsertHeap(struct HeapSq* HBT, ElemType x)
{
int i;
if (HBT->len == HBT->MaxSize) //若堆滿，將數組空間擴展為原來的2倍
{
ElemType *p;
p = realloc(HBT->heap, 2*HBT->MaxSize*sizeof(ElemType));
if (!p)
{
printf("存儲空間用完！\n");
exit(1);
}
printf("存儲空間已擴展為原來的2倍！\n");
HBT->heap = p;
HBT->MaxSize = 2*HBT->MaxSize;
}
HBT->heap[HBT->len] = x; //向堆尾添加新元素
HBT->len++; //堆長度加1
i = HBT->len - 1; //i指向待調整元素的位置，即其數組下標，初始指向新元素所在的堆尾位置
while (i != 0)
{
int j = (i - 1) / 2; //j指向下標為i的元素的雙親
if (x >= HBT->heap[j]) //若新元素大於待調整元素的雙親，則比較調整結束，退出循環
break;
HBT->heap[i] = HBT->heap[j]; //將雙親元素下移到待調整元素的位置
i = j; //使待調整位置變為其雙親位置，進行下一次循環
}
HBT->heap[i] = x;//把新元素調整到最終位置
}
//5、從堆中刪除堆頂元素並返回
ElemType DeleteHeap(struct HeapSq* HBT)
{
ElemType temp, x;
int i, j;
if (HBT->len == 0)
{
printf("堆已空，退出運行！\n");
exit(1);
}
temp = HBT->heap[0]; //暫存堆頂元素
HBT->len--;
if (HBT->len == 0) //若刪除操作後堆為空則返回
return temp;
x = HBT->heap[HBT->len]; //將待調整的原堆尾元素暫存x中，以便放入最終位置
i = 0; //用i指向待調整元素的位置，初始指向堆頂位置
j = 2 * i + 1;//用j指向i的左孩子位置，初始指向下標為1的位置
while (j <= HBT->len - 1)//尋找待調整元素的最終位置，每次使孩子元素上移一層，調整到孩子為空時止
{
if (j < HBT->len - 1 && HBT->heap[j] > HBT->heap[j+1])//若存在右孩子且較小，使j指向右孩子
j++;
if (x <= HBT->heap[j]) //若x比其較小的孩子還小，則調整結束，退出循環
break;
HBT->heap[i] = HBT->heap[j];//否則，將孩子元素移到雙親位置
i = j; //將待調整位置變為其較小的孩子位置
j = 2 * i + 1;//將j變為新的待調整位置的左孩子位置，繼續下一次循環
}
HBT->heap[i] = x; //把x放到最終位置
return temp; //返回原堆頂元素
}
//主函數
void main()
{
int i, x;
int a[8] = {23,56,40,62,38,55,10,16};
struct HeapSq b;
InitHeap(&b, 5);
for (i = 0; i < 8; i++)
InsertHeap(&b, a[i]);
while (!EmptyHeap(&b)) //依次刪除堆頂元素並顯示出來，直到堆空為止
{
x = DeleteHeap(&b);
printf("%d", x);
if (!EmptyHeap(&b))
printf(",");
}
printf("\n");
ClearHeap(&b);
}
運行結果：
分析：
（1）講下堆的插入操作：
向堆中插入一個元素時，首先將該元素寫入到堆尾，即堆中最後一個元素後面（下標為 len 的位置上），然後調整為一個新堆。
調整方法：若新元素小於雙親結點的值，就讓它們互換位置，新元素換到雙親位置後，使得以該位置為根的子樹稱為堆；
然後再對該位置與其雙親結點的值比較，做同樣的調整，直到以新位置的雙親結點為根仍是一個堆，或者調整到堆頂為止，此時整個樹變稱為了一個堆。
上面的程序，依次將數組[23,56,40,62,38,55,10,16]的中的元素插入堆，插入過程如下：
我們拿其中一個步驟具體分析，比如插入最後一個元素16時，插入之前的示意圖為上圖中的倒數第二個圖，在此圖的基礎上，將16插入堆尾，即62的左孩子位置，
此時16比其雙親62小，則使其與62互換位置，而此時16又比它所處的新位置的雙親38小，則再與38互換，最後此時16比它所處的新位置的雙親10大，則調整結束，
最後結果即為上圖中的最後一個圖所示。
（2）講下堆的刪除操作
刪除操作是刪除堆頂元素，留下的堆頂位置由堆尾位置填補，然後將其調整為一個新堆，
調整方法：新的堆頂元素值若大於兩個孩子結點中的最小值，就將它與具有最小值的孩子結點互換位置，
在被換到孩子結點位置後，再對此位置與其孩子結點最小值比較，進行同樣的調整，
直到以調整後的位置為根的子樹稱為一個堆，或者調整到葉子結點為止。
上面的程序依次刪除堆頂元素的過程如下：
我們拿其中一個具體分析，如刪除第一個堆頂元素10時，刪除之前的示意圖為上圖中的第一個圖，在此圖的基礎上，將10刪除，然後將堆尾元素62放在堆頂，
此時，62比其所在位置的孩子的最小值16大，則將其與16位置互換，而此時62又比其所在位置的孩子的最小值38大，則將其與38位置互換，此時的62所在的位置是
葉子結點，調整結束，最後的結果為上圖中的第二個圖所示。
