一、堆的概念及結(jié)構(gòu)

堆(Heap)是一種特殊的非線性結(jié)構(gòu)。堆中的元素是按完全二叉樹的順序存儲方式存儲在數(shù)組 中。滿足任意結(jié)點(diǎn)的值都大于等于左右子結(jié)點(diǎn)的值，叫做大堆，或者大根堆；反之，則是小堆，或者小根堆。

不熟悉二叉樹的小伙伴可以先跳轉(zhuǎn)→二叉樹詳解←學(xué)習(xí)。

堆分為小根堆和大根堆。

小根堆：所有父結(jié)點(diǎn)都小于等于左右孩子結(jié)點(diǎn)。
大根堆：所有父結(jié)點(diǎn)都大于等于左右孩子結(jié)點(diǎn)。

堆的性質(zhì)：

1.堆是一棵完全二叉樹。
2.堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值。
3.如果一個堆為大（小）根堆，則它的左右子樹也都是大（小）根堆。
4.小堆的存儲結(jié)構(gòu)不是升序，大堆的存儲結(jié)構(gòu)也不是降序。
5.堆中任意結(jié)點(diǎn)下標(biāo)為 i，則它的左孩子結(jié)點(diǎn)下標(biāo)為2i+1，右孩子結(jié)點(diǎn)下標(biāo)為2i+2，父結(jié)點(diǎn)下標(biāo)為(i-1)/2。

二、堆的實(shí)現(xiàn)

堆的兩個重要算法：向上調(diào)整和向下調(diào)整。

1.向上調(diào)整算法

向上調(diào)整一般在堆中插入元素時使用。

具體實(shí)現(xiàn)(小根堆示例)：
1.給定一個數(shù)組和一個結(jié)點(diǎn)下標(biāo)，該結(jié)點(diǎn)與其父結(jié)點(diǎn)的值進(jìn)行比較。
2.如果該結(jié)點(diǎn)的值 ≥ 其父結(jié)點(diǎn)的值，已經(jīng)是小堆了，則不再繼續(xù)調(diào)整；
3.如果該結(jié)點(diǎn)的值 < 其父結(jié)點(diǎn)的值，需要將二者交換，然后將父結(jié)點(diǎn)當(dāng)做孩子結(jié)點(diǎn)，繼續(xù)向上對比和交換，直到調(diào)整到堆頂。

如果是小根堆，只需要改變判斷符號>改為<即可。

//小根堆 向上調(diào)整
void AdjustUp(DataType* a, int child)
{int parent = (child - 1) / 2;//父結(jié)點(diǎn)下標(biāo)while (a[child] < a[parent])//建大堆{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}
}
//交換函數(shù)
void Swap(DataType* p1, DataType* p2)
{DataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

向上調(diào)整算法的比較次數(shù)最多不超過二叉樹的高度，所以時間復(fù)雜度為O(logN)

2.向下調(diào)整算法

堆的向下調(diào)整算法比較常用，堆排序和堆的創(chuàng)建都會用到向下調(diào)整算法。

向下調(diào)整算法有一個前提：左右子樹必須是一個堆，才能調(diào)整。

具體實(shí)現(xiàn)(小根堆示例)：
1.從該結(jié)點(diǎn)開始，與其左右孩子結(jié)點(diǎn)中比較大（較小）的結(jié)點(diǎn)進(jìn)行比較。
2.如果該結(jié)點(diǎn)的值 ≤ 其較小（較大）孩子結(jié)點(diǎn)的值，已經(jīng)是小堆了，則不再繼續(xù)調(diào)整；
3.如果該結(jié)點(diǎn)的值 > 其較小（較大）孩子結(jié)點(diǎn)的值，需要將二者交換，然后將較小的孩子結(jié)點(diǎn)當(dāng)做父結(jié)點(diǎn)，繼續(xù)向下對比和交換，直到調(diào)整到葉子結(jié)點(diǎn)。

//向下調(diào)整
void AdjustDown(DataType* a, int parent, int n)
{int child = 2 * parent + 1;while (child < n){//選出較小的孩子if (child + 1 < n && a[child + 1] < a[child])//右孩子不能越界訪問，注意判斷順序不能反{child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}

同樣，向下調(diào)整算法的比較次數(shù)最多也不會超過二叉樹的高度，所以時間復(fù)雜度為O(logN)

3.堆的創(chuàng)建

給定一個數(shù)組，怎么創(chuàng)建成一個堆呢？ 根結(jié)點(diǎn)的左右子樹都不是堆，該怎么調(diào)整？

向上調(diào)整建堆：

從根結(jié)點(diǎn)開始調(diào)整

從根結(jié)點(diǎn)的左孩子結(jié)點(diǎn)開始（因?yàn)楦Y(jié)點(diǎn)本身可以看做一個堆），每個結(jié)點(diǎn)都向上調(diào)整，此時該結(jié)點(diǎn)前面的所有結(jié)點(diǎn)都已經(jīng)構(gòu)成了一個堆，直到調(diào)整到最后一個結(jié)點(diǎn)，就可以調(diào)整成堆。

// 向上調(diào)整建堆 效率O(N*logN)
for (int i = 1; i < n; i++)
{AdjustUp(a, i);
}

向上調(diào)整建堆的時間復(fù)雜度是多少？

每個結(jié)點(diǎn)最多需要向上調(diào)整的次數(shù)與層數(shù)有關(guān)，若層數(shù)為k，則最多最多向上調(diào)整logk次。而隨著層數(shù)越大，每層的結(jié)點(diǎn)數(shù)也越多。假設(shè)二叉樹的高度為h，則向上調(diào)整為堆最多需要調(diào)整的次數(shù)為0×2⁰+1×2¹+2×2²+3×2³+…+(h-1)×2^h-1
= (h-2)×2^h（錯位相減，高中知識，具體過程略），又因?yàn)闃涞母叨萮=log(n+1)，所以時間復(fù)雜度的量級為O(N*logN)。

向下調(diào)整建堆：

從最后一個非葉子結(jié)點(diǎn)開始倒著調(diào)整

因?yàn)橄蛳抡{(diào)整建堆需要滿足左右子樹都是堆的前提，所以我們可以從最后一個結(jié)點(diǎn)開始依次向下調(diào)整，因?yàn)樽詈笠粋€結(jié)點(diǎn)本身可以看做是一個堆。但是因?yàn)?strong>葉子結(jié)點(diǎn)向下調(diào)整并不會發(fā)生變化，所以我們可以優(yōu)化代碼，從最后一個葉子結(jié)點(diǎn)的父結(jié)點(diǎn)也就是最后一個非葉子結(jié)點(diǎn)開始調(diào)整。

//向下調(diào)整建堆 效率O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(a, i, n);
}

向下調(diào)整建堆的時間復(fù)雜度是多少？

因?yàn)橄蛳抡{(diào)整建堆是從最后一個非葉子結(jié)點(diǎn)開始倒著調(diào)整的，隨著層數(shù)的減小，每層的結(jié)點(diǎn)數(shù)也越少，但是結(jié)點(diǎn)向下調(diào)整的次數(shù)在增加，具體推導(dǎo)過程這里不過多介紹，最后的時間復(fù)雜度的量級是O(N)。

綜上所述，向上調(diào)整建堆的時間復(fù)雜度為O(N*logN)，向下調(diào)整建堆的時間復(fù)雜度為O(N)，所以使用向下調(diào)整建堆的效率更高效。實(shí)際應(yīng)用中，一般都使用向下調(diào)整算法建堆。

堆的定義、初始化、銷毀
堆是以數(shù)組的方式存儲的，所以堆的定義、初始化、銷毀和順序表一樣。

#define INIT_SZ 10//初始空間大小
#define INC_SZ 4	//每次擴(kuò)容的數(shù)量
typedef int HDataType;
typedef struct Heap
{HDataType* a;int size;int capacity;
}Heap;//初始化
void HeapInit(Heap* php)
{assert(php);php->a = (HDataType*)malloc(sizeof(HDataType) * INIT_SZ);if (NULL == php->a){perror("malloc");return;}php->size = 0;php->capacity = INIT_SZ;
}//銷毀
void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

4.堆的插入

堆的插入需要用到向上調(diào)整算法。

實(shí)現(xiàn)步驟：
1.在堆的末尾插入一個元素；
2.該元素向上調(diào)整，直到滿足堆的性質(zhì)。

//入堆
void HeapPush(Heap* php, HDataType x)
{assert(php);//擴(kuò)容if (php->size == php->capacity){HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * (INC_SZ + php->capacity));if (NULL == tmp){perror("malloc");return;}php->a = tmp;php->capacity += INC_SZ;}php->a[php->size++] = x;//尾插AdjustUp(php->a, php->size - 1);//向上調(diào)整
}

5.堆的刪除

刪除的是堆頂?shù)脑?#xff0c;刪除之后仍然保證是堆
堆的刪除需要用到向下調(diào)整算法。

實(shí)現(xiàn)步驟：
1.將堆頂元素與最后一個元素交換；
2.堆長度-1，即刪除最后一個位置；
3.將交換后的堆頂元素向下調(diào)整。

void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));//將尾數(shù)據(jù)和堆頂數(shù)據(jù)交換，交換后的堆頂元素再向下調(diào)整Swap(&php->a[php->size - 1], &php->a[0]);php->size--;//堆的有效長度-1AdjustDown(php->a, 0, php->size);
}

6.堆的其他操作

//返回堆頂元素
HDataType HeapTop(Heap* php)
{assert(php);return php->a[0];
}
//判堆空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}
//堆的元素個數(shù)
int HeapSize(Heap* php)
{assert(php);return php->size;
}

三、堆的應(yīng)用

1.堆排序

從前面的學(xué)習(xí)我們知道，堆結(jié)構(gòu)的層序遍歷，也就是從上到下每一層的從左到右，并非是有序的，也就是說堆存儲在數(shù)組中的數(shù)據(jù)并不是有序的。比如下面這個大根堆，在數(shù)組中就是10,5,9,4,3,1,7 我們?nèi)绾卫枚训奶匦詫⑦@些數(shù)據(jù)排序呢？

我們知道，大根堆的堆頂一定是最大的，小根堆的堆頂一定是最小的，所以利用這一個特點(diǎn)，我們可以取出堆頂元素，然后將剩下的元素重新調(diào)整成堆，再取堆頂元素，再調(diào)整剩下的元素，依次類推直到最后一個元素，就可以實(shí)現(xiàn)堆排序了。

但是，如果我們將堆頂元素按兵不動，將剩下的元素原地調(diào)整成堆，但剩下的元素會被完全打亂，完全不符合堆的性質(zhì)，需要重新建堆，最后雖然也可以排序，但是效率卻很低。這樣的話跟普通排序沒什么區(qū)別，每次找最大值（最小值）就好了，并沒有用到堆的優(yōu)勢。

堆排序的實(shí)現(xiàn)步驟：
1.先將數(shù)組建堆；
2.將堆頂元素與堆末尾元素交換；
3.堆有效長度-1；
4.再將堆頂元素向下調(diào)整，直到調(diào)整到成堆

這不就是先建一個堆，再進(jìn)行堆的刪除操作嗎？沒毛病，原理是一樣的。

比如一個大根堆，我們?nèi)〕龆秧斣?#xff08;最大數(shù)）與最后一個數(shù)交換，交換后的最大數(shù)不看作在堆里面，那么堆頂元素的左右子樹仍滿足堆的性質(zhì)，堆的結(jié)構(gòu)并沒有被破壞，然后堆頂元素向下調(diào)整成堆，即可選出第二大的數(shù)，以此類推到最后一個元素，就可以成功實(shí)現(xiàn)堆排序了。

堆排序就是每次將堆頂元素從數(shù)組的末尾往前放，所以排升序建大堆，排降序建小堆

//堆排序
void HeapSort(int* a, int n)
{//建堆：排升序建大堆，排降序建小堆//倒著調(diào)整，從最后一個非葉子結(jié)點(diǎn)開始向下調(diào)整建堆 效率O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}//O(N*logN)int end = n - 1;//堆的有效長度while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;}
}

堆排序的時間復(fù)雜度是O(N*logN)

2.Top-K問題

Top-K問題：求集合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：游戲中排行榜前50名，全校前10名等。

對于Top-K問題，自然第一個想到的就是排序，沒毛病。但是數(shù)據(jù)量很大的情況下，排序就不太可取了(可能
數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。

第二種方法就是用堆來解決。

實(shí)現(xiàn)方法：

1. 用數(shù)據(jù)集合中前K個元素來建堆。
   ?前k個最大的元素，則建小堆
   ?前k個最小的元素，則建大堆
2. 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素。比較完后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。

如果選前k個最大值，需要建小堆。
原理分析：小堆的堆頂元素是這k個數(shù)據(jù)中最小的元素，如果剩下N-K個元素中有大于堆中最小值的，說明這個數(shù)可以進(jìn)入前k名；如果剩下N-K個元素中有小于堆中最小值的，則無法進(jìn)入前k名。但是如果建大堆的話，堆頂元素就無法作為標(biāo)準(zhǔn)了。

void TopK(int* a, int n, int k)
{//用a中前k個元素建堆for (int i = (k - 2) / 2; i >= 0; i--)AdjustDown(a, i, k);for (int i = k; i < n; i++){if (a[i] < a[0]){Swap(&a[i], &a[0]);//不滿足則交換AdjustDown(a, 0, k);//向下調(diào)整}}for (int i = 0; i < k; i++)printf("%d ", a[i]);
}

上述代碼只是選出前k個最大值或最小值，并沒有將這k個數(shù)排序，如果要實(shí)現(xiàn)排序功能自行添加即可。

堆的完整代碼放在gitee：https://gitee.com/ncu-ball/study/tree/master/24_4_19