引言

什么是堆？堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)（用數(shù)組表示的樹）。

為什么要使用到堆？比如一場比賽，如果使用擂臺賽的方式來決出冠軍（實(shí)力第一），就很難知道實(shí)力第二的隊(duì)伍是什么了。

但是下圖能很清楚的表示各隊(duì)伍的強(qiáng)弱關(guān)系。

堆的特點(diǎn)

上圖就是一個最大堆，解釋：每一個圓都是一個節(jié)點(diǎn)，數(shù)字代表著鍵值，其中95是93和92的父節(jié)點(diǎn)，93和92是95的子節(jié)點(diǎn)，93和92是兄弟節(jié)點(diǎn)（父節(jié)點(diǎn)為同一個），根節(jié)點(diǎn)就是鍵值最大的節(jié)點(diǎn)，為95，最后一個節(jié)點(diǎn)是87，最后一個左子節(jié)點(diǎn)也是87。

最大堆的特點(diǎn)：

滿足以下三點(diǎn)

1.每個節(jié)點(diǎn)最多可以有兩個子節(jié)點(diǎn)。

2.根節(jié)點(diǎn)的鍵值是所有堆節(jié)點(diǎn)鍵值中最大者，且每個節(jié)點(diǎn)的值都大于其子（孩子）節(jié)點(diǎn)。

3.除了根節(jié)點(diǎn)沒有兄弟節(jié)點(diǎn)，最后一個左子節(jié)點(diǎn)可以沒有兄弟節(jié)點(diǎn)，其他節(jié)點(diǎn)必須有兄弟節(jié)點(diǎn)。

最好是自己理解，不用強(qiáng)記 。其中有一點(diǎn)要注意：A的兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)可能大于A，相當(dāng)于在比賽中，其中一個小組都是弱隊(duì)，那么一個弱隊(duì)卻可以闖入半決賽一樣。

最小堆的特點(diǎn)的話就將第二點(diǎn)中的大改為小就可以了，其他的特點(diǎn)一樣。這里討論的是最大堆

數(shù)組形式表示

父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系：

i 的左子節(jié)點(diǎn)：2i+1 ，右子節(jié)點(diǎn)：2i+2

i 的父節(jié)點(diǎn)：（i-1）/2

i 是從 0 開始的

再將上圖的堆轉(zhuǎn)換為數(shù)組的形式，如下圖：

?這就是一個最大堆的數(shù)組表示形式。

在數(shù)組中快速創(chuàng)建堆

也就是怎么把任意一個數(shù)組變成最大/小堆。

我們先把堆的最小單位拿出來，如下圖：

他不是一個最大堆，如果要變成最大堆，只需要父節(jié)點(diǎn)是95，子節(jié)點(diǎn)分別是86、88就可以了（86和95交換）。而一個最大堆是由若干個這個最小單位組成的，所以第一步就是將所有的堆的最小單位變成最大堆。

1、首先先找到最后一個節(jié)點(diǎn)的父節(jié)點(diǎn)，找出該節(jié)點(diǎn)的最大子節(jié)點(diǎn)與自己比較，如果大于自身，就交換兩個節(jié)點(diǎn)。

2、繼續(xù)移動到上一個父節(jié)點(diǎn)（也就是下標(biāo) -1 的地方），重復(fù)做第一步的比較操作，直到遍歷所有的父節(jié)點(diǎn)。

當(dāng)我們移動完所有的父節(jié)點(diǎn)，那最大堆就形成了嗎？還疏忽了一個地方。例如當(dāng)移動到某個父節(jié)點(diǎn)時，如下圖：

最開始父節(jié)點(diǎn)是88，與子節(jié)點(diǎn)95交換了，那父節(jié)點(diǎn)就是95，95 的子節(jié)點(diǎn)就是 88，那88一定大于他的子節(jié)點(diǎn)嗎？很顯然這個答案是不一定，因?yàn)?88 的子節(jié)點(diǎn)只滿足小于之前的父節(jié)點(diǎn) 95，所以還需要向下調(diào)整，直到子節(jié)點(diǎn)都小于父節(jié)點(diǎn)。

3、對每次移動中，變成子節(jié)點(diǎn)的節(jié)點(diǎn)，向下調(diào)整，也就是判斷他與子節(jié)點(diǎn)是否滿足最大堆的特點(diǎn)，不滿足還要繼續(xù)移動節(jié)點(diǎn)（向下調(diào)整），滿足的話就接著下個父節(jié)點(diǎn)。

4、所有的節(jié)點(diǎn)交換完畢，最大堆構(gòu)建完成。

堆的算法實(shí)現(xiàn)

堆數(shù)據(jù)結(jié)構(gòu)的定義

#define DEFAULT_CAPCITY 120 //默認(rèn)的堆容量typedef struct _Heap
{int* arr;		//存儲堆元素的數(shù)組int size;		//堆中元素的個數(shù)int capcity;	//堆的容量
}Heap;//函數(shù)聲明
void buildHeap(Heap& heap);
bool inset(Heap& heap, int value);
bool initHeap(Heap& heap, int* orginal, int size);
void adjustDown(Heap& heap, int i);
void adjustUp(Heap& heap, int i);

堆的初始化?

bool initHeap(Heap& heap,int *orginal,int size) 
{//orginal 是指向數(shù)組的指針，而這個數(shù)組是我們要傳入堆的數(shù)組int capcity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size; //取size和默認(rèn)容量的最大值heap.arr = new int[capcity];if (!heap.arr) return false; //申請失敗heap.capcity = capcity;if (size > 0) //size合法{memcpy(heap.arr, orginal, sizeof(int) * size);heap.size = size;//建堆buildHeap(heap);}return true;
}

堆的創(chuàng)建

//建堆，從最后一個父節(jié)點(diǎn)逐個向前調(diào)整所有的父節(jié)點(diǎn)（直到根節(jié)點(diǎn)），確保每一個父節(jié)點(diǎn)都是一個最大堆
//那么，整體上就是一個最大堆
void buildHeap(Heap& heap)
{int i = (heap.size - 2) / 2; //因?yàn)橄聵?biāo)從0開始，heap.size-1就得到下標(biāo)，再結(jié)合公式就是這個式子for (; i >= 0; i--){adjustDown(heap, i); //向下調(diào)整包含了構(gòu)建最大堆，如果感到困惑，先看向下調(diào)整函數(shù)}
}

堆的向下調(diào)整函數(shù)

void adjustDown(Heap& heap, int i)
{int temp = heap.arr[i]; //保存父節(jié)點(diǎn)的鍵值int parent = 0 ,child = 0;for (parent = i; (2 * parent + 1) < heap.size; parent = child) {child = 2 * parent + 1; //先指向左子節(jié)點(diǎn)//指向兩個子節(jié)點(diǎn)中最大的節(jié)點(diǎn)if (child + 1 < heap.size && heap.arr[child] < heap.arr[child + 1]){child = child + 1;}if (temp >= heap.arr[child]){break; //無需向下調(diào)整}else{heap.arr[parent] = heap.arr[child];heap.arr[child] = temp;}}
}

堆的插入新元素

1、插入新的元素到最大堆的尾部，也就是數(shù)組的后面

2、插入的元素可能會破環(huán)這個最大堆，需要重新調(diào)整，和父節(jié)點(diǎn)比較，如果比父節(jié)點(diǎn)大，就交換兩個節(jié)點(diǎn)……重復(fù)直到新節(jié)點(diǎn)比父節(jié)點(diǎn)小或者新節(jié)點(diǎn)變?yōu)楦?jié)點(diǎn)（調(diào)整到位）。

設(shè)計(jì)兩個函數(shù)，一個是插入，一個是向上調(diào)整。

bool insert(Heap& heap, int value)
{if (heap.size == heap.capcity) //堆空間不足{return false;}int i = heap.size ; //指向新加元素的下標(biāo)heap.arr[heap.size++] = value;adjustUp(heap , i);return true;
}

void adjustUp(Heap& heap, int i)
{if (i <= 0 || i >= heap.size) return;while (i > 0){int parent = (i - 1) / 2;if (parent >= 0) // 父節(jié)點(diǎn)沒越界{if (heap.arr[parent] < heap.arr[i]){int temp = heap.arr[i];heap.arr[i] = heap.arr[parent];heap.arr[parent] = temp;i = parent;}else{break; //無需調(diào)整}}else{break; //父節(jié)點(diǎn)出界}}
}

看到這，你會發(fā)現(xiàn)堆的創(chuàng)建還有一種方式，也就是將數(shù)組的元素一個一個插入，也能得到最大堆。

源代碼

#include <iostream>using namespace std;#define DEFAULT_CAPCITY 120 //默認(rèn)的堆容量typedef struct _Heap
{int* arr;		//存儲堆元素的數(shù)組int size;		//堆中元素的個數(shù)int capcity;	//堆的容量
}Heap;void buildHeap(Heap& heap);
bool insert(Heap& heap, int value);
bool initHeap(Heap& heap, int* orginal, int size);
void adjustDown(Heap& heap, int i);
void adjustUp(Heap& heap, int i);//初始化堆
bool initHeap(Heap& heap,int *orginal,int size) 
{//orginal 是指向數(shù)組的指針，而這個數(shù)組是我們要傳入堆的數(shù)據(jù)int capcity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size; //取size和默認(rèn)容量的最大值heap.arr = new int[capcity];if (!heap.arr) return false;heap.capcity = capcity;if (size > 0){memcpy(heap.arr, orginal, sizeof(int) * size);heap.size = size;//建堆buildHeap(heap);}return true;
}//建堆，從最后一個父節(jié)點(diǎn)逐個向前調(diào)整所有的父節(jié)點(diǎn)（直到根節(jié)點(diǎn)），確保每一個父節(jié)點(diǎn)都是一個最大堆
//那么，整體上就是一個最大堆
void buildHeap(Heap& heap)
{int i = (heap.size - 2) / 2; //因?yàn)橄聵?biāo)從0開始，heap.size-1就得到下標(biāo)for (; i >= 0; i--){adjustDown(heap, i);}
}void adjustDown(Heap& heap, int i)
{int temp = heap.arr[i]; //父節(jié)點(diǎn)的鍵值int parent = 0 ,child = 0;for (parent = i; (2 * parent + 1) < heap.size; parent = child){child = 2 * parent + 1;//指向兩個子節(jié)點(diǎn)中最大的節(jié)點(diǎn)if (child + 1 < heap.size && heap.arr[child] < heap.arr[child + 1]){child = child + 1;}if (temp >= heap.arr[child]){break; //無需向下調(diào)整}else{heap.arr[parent] = heap.arr[child];heap.arr[child] = temp;}}
}//堆——插入新元素
bool insert(Heap& heap, int value)
{if (heap.size == heap.capcity){return false;}int i = heap.size ;heap.arr[heap.size++] = value;adjustUp(heap , i);return true;
}void adjustUp(Heap& heap, int i)
{if (i <= 0 || i >= heap.size) return;while (i > 0){int parent = (i - 1) / 2;if (parent >= 0) // 父節(jié)點(diǎn)沒越界{if (heap.arr[parent] < heap.arr[i]){int temp = heap.arr[i];heap.arr[i] = heap.arr[parent];heap.arr[parent] = temp;i = parent;}else{break; //無需調(diào)整}}else{break; //父節(jié)點(diǎn)出界}}
}
int main(void)
{Heap heap;int orginalArr[] = { 1,2,3,87,93,82,92,86,95 };if (!initHeap(heap, orginalArr, sizeof(orginalArr) / sizeof(int))){cout << "初始化堆失敗！" << endl;exit(-1);}for (int i = 0; i < heap.size; i++){printf("%d\n",heap.arr[i]);}puts("");insert(heap, 100);for (int i = 0; i < heap.size; i++){printf("%d\n", heap.arr[i]);}return 0;
}