引言

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

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

但是下圖能很清楚的表示各隊伍的強弱關系。

堆的特點

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

最大堆的特點：

滿足以下三點

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

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

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

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

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

數(shù)組形式表示

父節(jié)點和子節(jié)點的關系：

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

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

i 是從 0 開始的

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

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

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

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

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

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

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

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

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

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

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

4、所有的節(jié)點交換完畢，最大堆構建完成。

堆的算法實現(xiàn)

堆數(shù)據(jù)結構的定義

#define DEFAULT_CAPCITY 120 //默認的堆容量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和默認容量的最大值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ào)整所有的父節(jié)點（直到根節(jié)點），確保每一個父節(jié)點都是一個最大堆
//那么，整體上就是一個最大堆
void buildHeap(Heap& heap)
{int i = (heap.size - 2) / 2; //因為下標從0開始，heap.size-1就得到下標，再結合公式就是這個式子for (; i >= 0; i--){adjustDown(heap, i); //向下調(diào)整包含了構建最大堆，如果感到困惑，先看向下調(diào)整函數(shù)}
}

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

void adjustDown(Heap& heap, int i)
{int temp = heap.arr[i]; //保存父節(jié)點的鍵值int parent = 0 ,child = 0;for (parent = i; (2 * parent + 1) < heap.size; parent = child) {child = 2 * parent + 1; //先指向左子節(jié)點//指向兩個子節(jié)點中最大的節(jié)點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é)點比較，如果比父節(jié)點大，就交換兩個節(jié)點……重復直到新節(jié)點比父節(jié)點小或者新節(jié)點變?yōu)楦?jié)點（調(diào)整到位）。

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

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é)點沒越界{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é)點出界}}
}

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

源代碼

#include <iostream>using namespace std;#define DEFAULT_CAPCITY 120 //默認的堆容量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和默認容量的最大值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ào)整所有的父節(jié)點（直到根節(jié)點），確保每一個父節(jié)點都是一個最大堆
//那么，整體上就是一個最大堆
void buildHeap(Heap& heap)
{int i = (heap.size - 2) / 2; //因為下標從0開始，heap.size-1就得到下標for (; i >= 0; i--){adjustDown(heap, i);}
}void adjustDown(Heap& heap, int i)
{int temp = heap.arr[i]; //父節(jié)點的鍵值int parent = 0 ,child = 0;for (parent = i; (2 * parent + 1) < heap.size; parent = child){child = 2 * parent + 1;//指向兩個子節(jié)點中最大的節(jié)點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é)點沒越界{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é)點出界}}
}
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;
}