二叉堆
二叉堆是一棵完全二叉樹胡野，什么是完全二叉樹呢？簡(jiǎn)單來(lái)說(shuō)硫豆，就是按照層的順序笼呆，對(duì)樹的節(jié)點(diǎn)標(biāo)號(hào)，然后按照層次遍歷的順序來(lái)遍歷诗赌，得到的結(jié)果是按照順序來(lái)標(biāo)號(hào)的汗茄，不能出現(xiàn)斷點(diǎn)铭若，這就是一個(gè)完全二叉樹。這么說(shuō)比較抽象瞳腌，舉個(gè)例子來(lái)說(shuō)镜雨。
這個(gè)二叉樹的層次遍歷結(jié)果是0，1荚坞，2挑宠，3西剥，4亿汞，5，6，7南捂，8.所以是一個(gè)完全二叉樹旧找。
這里這棵二叉樹進(jìn)行層次遍歷溺健，得到就是0钮蛛，1，2岭辣，3，4沦童，5叹话，6偷遗，7驼壶，10.編號(hào)不是連續(xù)的，就不是一棵完全二叉樹箩溃。
堆就是一棵完全二叉樹碌嘀，不過(guò)因?yàn)橥耆鏄涞奶匦曰林迹趯?shí)現(xiàn)它的時(shí)候往往不是使用鏈表股冗，而是使用數(shù)組來(lái)實(shí)現(xiàn)，我們可以把上面的二叉樹的節(jié)點(diǎn)標(biāo)號(hào)與數(shù)組的下標(biāo)對(duì)應(yīng)起來(lái)止状。二叉樹的根節(jié)點(diǎn)標(biāo)號(hào)從1開始，存儲(chǔ)的數(shù)組也從下標(biāo)1開始存儲(chǔ)二叉樹怯疤，一一對(duì)應(yīng)，這種情況下伏社，父節(jié)點(diǎn)的數(shù)組下標(biāo)為i，則左子樹的數(shù)組下標(biāo)為2i摘昌，右子樹的下標(biāo)為2i+1(如果沒(méi)有超出數(shù)組的界限的情況下)
上圖的二叉樹將被存儲(chǔ)為下面的數(shù)組
在程序里就是如下的訪問(wèn)子節(jié)點(diǎn)和父節(jié)點(diǎn)。
int heap[10];
//訪問(wèn)第三個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
heap[3/2];
//訪問(wèn)第三個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)
heap[3*2]
//訪問(wèn)第三個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)
heap[3*2+1]
如果是最大堆罕容，那么父節(jié)點(diǎn)都要比兩個(gè)子節(jié)點(diǎn)的數(shù)值大稿饰，相應(yīng)的最小堆就是父節(jié)點(diǎn)比兩個(gè)子節(jié)點(diǎn)都要小。而哨兵的作用就是充當(dāng)邊界檢測(cè)的角色喉镰。如果是最大堆，那么這個(gè)值比堆中的數(shù)據(jù)都要大梧喷，如果是最小堆，那么這個(gè)值比堆中所有數(shù)據(jù)都要小汇歹。
堆的程序?qū)崿F(xiàn)
堆的結(jié)構(gòu)定義
typedef int Element;
typedef struct HeapNode
{
int heapsize; //堆的最大尺寸偿凭，也就是數(shù)組的最大值
int size;//堆的當(dāng)前大小
Element *data;//數(shù)組指針产弹，動(dòng)態(tài)分配數(shù)組的大小
};
typedef struct HeapNode* Heap;//堆的指針定義
#define MIN_DATA -20000 //這里實(shí)現(xiàn)最小堆弯囊，哨兵是最小值，堆中數(shù)據(jù)的范圍是-10000匾嘱，10000，這個(gè)值隨需要更改
創(chuàng)建一個(gè)heapsize大小的堆
Heap creatHeap(int heapsize)
{
Heap heap;
heap=(Heap)malloc(sizeof(struct HeapNode));
if(heap==NULL)
{
printf("內(nèi)存不足");
return NULL;
}
heap->data=(Element*)malloc(sizeof(Element)*(heapsize+1));
if(heap->data==NULL)
{
printf("內(nèi)存不足");
return NULL;
}
heap->heapsize=heapsize;
heap->size=0;
heap->data[0]=MIN_DATA;
return heap;
}
判斷堆空或者堆滿
這個(gè)比較簡(jiǎn)單撬讽，因?yàn)槎咽且粋€(gè)數(shù)組悬垃，如果size變量為0，表示堆空尝蠕。如果size變量等于堆數(shù)組的最大值，那么就是堆滿看彼。
int isFull(Heap heap)
{
return heap->size==heap->heapsize;
}
int isEmpty(Heap heap)
{
return heap->size==0;
}
堆的插入操作
堆的插入操作就是首先將size變量加1昧捷，當(dāng)前節(jié)點(diǎn)i=size+1,然后訪問(wèn)它的父節(jié)點(diǎn)i/2罐寨，比較插入的元素和父節(jié)點(diǎn)的元素哪個(gè)元素行蚓亍（這里以最小堆為例),如果新插入的元素比較小，那么就將父節(jié)點(diǎn)i/2的值賦值到當(dāng)前節(jié)點(diǎn)i簸淀。此時(shí)將i更新（i=i/2)，然后去比較此時(shí)i的節(jié)點(diǎn)的父節(jié)點(diǎn)（i/2,相當(dāng)于（size+1）/4）與插入的元素舷手，直到比較到哨兵劲绪，因?yàn)樯诒亲钚≈担圆迦氲脑貢?huì)放到數(shù)組下標(biāo)的0的位置贾富。如果比較到其中某個(gè)位置時(shí)，插入的節(jié)點(diǎn)比父節(jié)點(diǎn)的大汗捡，那么就把插入的節(jié)點(diǎn)放到當(dāng)前位置畏纲。以圖說(shuō)話。
假設(shè)有如上的最小堆盗胀，堆目前的size是5，如果插入一個(gè)元素15簿训，則size加1米间，相當(dāng)于把31后面的數(shù)組位置空出來(lái)，等待插入屈糊，然后比較i=6的父節(jié)點(diǎn)i/2，此時(shí)是16夫晌，因?yàn)?5小于16，所以16就需要下移到數(shù)組下標(biāo)為6的位置了晓淀。
只是將16復(fù)制到了數(shù)組下標(biāo)為6的地方，數(shù)組下標(biāo)為3的值沒(méi)有改變燥爷，還是16.然后此時(shí)i移動(dòng)到位置3懦窘，比較i=3的父節(jié)點(diǎn)i/2，此時(shí)是數(shù)組的下標(biāo)1的數(shù)據(jù)畅涂，13<15，說(shuō)明符合最小堆的定義立宜，父節(jié)點(diǎn)小于子節(jié)點(diǎn)臊岸，所以15應(yīng)該插入到數(shù)組下標(biāo)為3的地方。插入完成扇单。
在比如在此時(shí)直接插入20元素蜘澜，size加1等于7施流，它的父節(jié)點(diǎn)的值為15鄙信，比20小，所以20直接放到數(shù)組下標(biāo)為7的位置银受。
插入操作的程序如下：
void insert(Heap heap,Element x)
{
int i=0;
if(isFull(heap))
{
printf("堆滿了");
return;
}
for(i=++heap->size;x<heap->data[i/2];i=i/2) //這里因?yàn)橛猩诒徊桑援?dāng)i等于0時(shí)，是一定會(huì)結(jié)束循環(huán)的渔伯，如果不使用哨兵，需要判斷一下i為0选浑，否則導(dǎo)致死循環(huán)
{
heap->data[i]=heap->data[i/2];
}
heap->data[i]=x;
}
堆的刪除操作
堆的刪除操作就是將數(shù)組的下標(biāo)1的數(shù)據(jù)返回，然后重新構(gòu)造堆古徒，將size減1，并將最后一個(gè)數(shù)據(jù)找到合理的位置插入代态。就是從根節(jié)點(diǎn)開始（也就是下標(biāo)1）找到兩個(gè)子節(jié)點(diǎn)的最小值舀寓，與最后一個(gè)數(shù)據(jù)比較肌蜻，如果最后一個(gè)數(shù)據(jù)比兩個(gè)子節(jié)點(diǎn)的最小值還要小的話，那么就把這個(gè)數(shù)據(jù)復(fù)制到這兩個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)蒋搜；如果最后一個(gè)數(shù)據(jù)比兩個(gè)子節(jié)點(diǎn)的最小值還要大的話，那么就將兩個(gè)子節(jié)點(diǎn)的最小值節(jié)點(diǎn)復(fù)制到它的父節(jié)點(diǎn)育谬，然后以這個(gè)子節(jié)點(diǎn)作為父節(jié)點(diǎn)帮哈，重復(fù)上述過(guò)程，直到找到合適位置娘侍。
假設(shè)執(zhí)行刪除操作，13刪除嚎杨，最后一個(gè)元素16被取出氧腰，size減1，比較13的子節(jié)點(diǎn)21和15古拴，15位最小的，那么比較15和16膏潮，發(fā)現(xiàn)15小满力，所以將15復(fù)制到13的位置轻纪。
此時(shí)以數(shù)組下標(biāo)3作為父節(jié)點(diǎn)叠纷，比較它的兩個(gè)子節(jié)點(diǎn)，但是發(fā)現(xiàn)已經(jīng)沒(méi)有了涩嚣，所以把16復(fù)制到數(shù)組下標(biāo)3的位置就完成了刪除操作。
假設(shè)第一次刪除13時(shí)顷歌，它的兩個(gè)子節(jié)點(diǎn)都比16大幔睬，那么直接將16復(fù)制到數(shù)組下標(biāo)為1的地方，就完成了刪除麻顶。這就是堆的刪除操作的執(zhí)行過(guò)程。
程序代碼如下：
Element deleteHeap(Heap heap)
{
int child,parent;
Element x,num;
if(isEmpty(heap))
{
printf("堆空");
return MIN_DATA;
}
x=heap->data[1];//保存要?jiǎng)h除的元素队萤，作為返回值
num=heap->data[heap->size--];//堆的尺寸小1矫钓，將這個(gè)數(shù)值保存以免丟失
for(parent=1;parent*2<=heap->size;parent=child)
{
child=2*parent;
//尋找兩個(gè)子節(jié)點(diǎn)中最小的一個(gè)，&&前面的判斷是防止child已經(jīng)是堆的最后一個(gè)數(shù)據(jù)新娜，加1后超出堆的范圍
if((child+1)<=heap->size&&heap->data[child]>heap->data[child+1])
{
child=child+1;
}
//比較兩個(gè)子節(jié)點(diǎn)的最小值和要原堆中最后一個(gè)元素，如果最后一個(gè)元素小匆帚，說(shuō)明找到了插入的位置旁钧，結(jié)束循環(huán)
if(num<=heap->data[child])
{
break;
}
else
{
heap->data[parent]=heap->data[child];
}
}
heap->data[parent]=num;
return x;
}
堆的構(gòu)建
將一個(gè)數(shù)組變成最小堆，思路就是從根本一個(gè)子樹一個(gè)子樹的逐漸變換歪今，假設(shè)數(shù)組大小為size，那么它的父節(jié)點(diǎn)就是i=size/2嫉晶，以i為起點(diǎn)，執(zhí)行與刪除操作相同的下濾操作替废，直到i變成0，就完成了堆的構(gòu)建诈火，其實(shí)就是堆排序的思路状答。
void perdown(Heap heap,int d)
{
int child,parent;
Element x;
x=heap->data[d];
for(parent=d;parent*2<=heap->size;parent=child)
{
child=2*parent;
if((child+1)<=heap->size&&heap->data[child]>heap->data[child+1])
{
child=child+1;
}
if(x<=heap->data[child])
{
break;
}
else
{
heap->data[parent]=heap->data[child];
}
}
heap->data[parent]=x;
}
void buildHeap(Heap heap)
{
int i=0;
for(i=heap->size/2;i>0;i--)
{
perdown(heap,i);
}
}
