一：堆的概念及儲存結構

簡單點來說，堆就是完全二叉樹，只不過這個完全二叉樹有個特點：它的結點要麼大於任意一個孩子結點，要麼小於任意一個孩子結點。如果其結點大於任意一個孩子結點，就稱其為大頂堆，反之如果其結點小於任意一個孩子結點，就稱其為小頂堆。

於是對於大頂堆來說，其值最大的結點是根節點，對小頂堆來說，其值最小的結點也是根節點。這一點也是堆排序演算法實現的核心，所以堆排序也叫做選擇排序。

既然它是完全二叉樹，所以適合用陣列來儲存

二：堆的實現（1）堆的結構體定義

堆是一個完全二叉樹，所以使用一個數組來儲存。儲存時為了便於調整，依然使用動態增長的陣列

（2）堆的初始化

使用堆的場景，或者是題目中一般是這樣給出的：直接拋給你一個數組，這個陣列對應了一個完全二叉樹，初始化時就是要把這個陣列進行復制，然後對這個二叉樹進行調整，使其成為堆，再進行後續操作。所以初始化引數裡，要給出陣列和元素個數

（3）堆的向下調整演算法

堆的調整演算法是堆的核心所在。上述陣列中的完全二叉樹還不是堆，這裡用上圖中的陣列，以調整小頂堆為例，詳細說明堆的調整過程基本思路如圖所示

調整程式碼如下

下面的這個動圖所展示的就是調整過程：

上述程式碼中，有一個非常容易忽略的地方

補充：上面構建的是小頂堆，如果要構建大頂堆，程式碼只需稍微改動兩個地方即可

（4）堆的構造

上面堆的向下調整演算法要求左右子樹必須是堆，但一般不會有這樣的理想情況。那麼為什麼還要講堆的向下調整演算法呢？其實對於一個完全二叉樹，從根節點角度看，確實滿足不了情況。但是，去考察極限情況——一個結點就是一個完全二叉樹，它也一定是一個堆，所以可以從最後一個非葉結點開始（也可以從最後一個結點開始，只不過，如果從最後一個結點開始效率不高），對每一個結點使用堆的向下調整，直到根節點，這樣就能構造一個小頂堆了。如果一個完全二叉樹有n個結點，那麼它的最後一個非葉結點的編號為(n/2)-1。

如下

程式碼如下

（5）堆排序A：堆排序思想

從上面的敘述可以看出，堆建立後，對應陣列是部分有序的，因為我們對堆元素大小的限制僅侷限於父結點和孩子結點之間，對於左孩子和右孩子之間誰大誰小是不關心的。

那麼堆排序從何而來呢？仔細觀察，雖然不能保障堆是完全有序的，但是卻能保證根結點是最大的（大頂堆）或最小的（小頂堆）。於是：我們可以每次選出一個根結點，將其劃到有序序列裡面，並對剩餘結點進行調整，使剩餘部分再次成為一個堆，然後對這個堆再進行上述操作，這也就是為什麼堆排序屬於選擇排序的原因。

這裡還有一個問題，當把根節點選出來後，剩餘部分就沒有根節點了，此時應該怎麼做？是把它們再搞成一個完全二叉樹，然後再進行建堆？仔細想想也不行，因為這樣做時間複雜度就太高了，堆排序也就沒有存在的意義了。這裡：選出根節點後，讓根節點與此時無序序列中的最後一個結點（第一次選擇的時候就和最後一個結點交換，第二次選擇的時候和倒數第二個結點交換，以此類推）進行交換，此時根節點到達下方成為有序序列中的一員，新的結點到達根節點位置，由於這個結點到來，堆的結構被破壞，由於是根節點破壞了堆的結構，所以呼叫向下調整函式，只對根節點的位置進行調整，重新生成一個堆，然後重複上述操作。

以小頂堆為例，經過上述操作，每次根節點到達有序序列的前一個位置，於是整個陣列成為了降序排列；以大頂堆為例，經過上述操作，整個陣列就成為了升序排列。於是就有：需要升序排序，就建立大頂堆，需要降序排序，就建立小頂堆。

B：堆排序演示

堆排序步驟：利用題目中給出的數字，建立完全二叉樹，然後對這個完全二叉樹進行建堆操作，接著根據題目要求，進行選擇，調整，選擇，調整······。

對本例的陣列建立大頂堆，進行升序排序，過程如下

C：堆排序程式碼D：堆排序時間複雜度

堆排序時間複雜度為：O(nlgn)

推導過程如下：

（5）插入元素

還是以上述大頂堆為例，建好堆後，需要插入元素，此新元素插入到最後一個結點的下一個位置，由於這一個結點的到來，可能再次破壞了堆的結果，所以可以重新建立堆，但是仔細觀察，其破壞的僅僅是一部分，如圖

與向下調整演算法相反，上圖涉及的是向上調整演算法，執行過程，程式碼與向下調整演算法恰好相反

三：Top K問題

Top K問題：找出N個數當中最大的或者最小的前K個

解決方法1：排序

對於大多數人，想到的第一個方法自然就是排序。把這個N個數按一定順序排序即可，然後找出取出前K個數。這種方法在N不太大的情況下是可以的，但是當N非常大的時，即便用最快的排序演算法，最後花費的時間代價還是很高的，是一種不明智的解法。而且當N非常非常大時，記憶體中無法放下，就不能使用如堆排序這樣的內部排序演算法

解決方法2：；建堆

其實這也是堆這種結構真正的用途所在假設用1萬億個數，需求是找出這一萬億個數中最大的前10個。，如果提示使用堆來解決，我們正常的反映就是建立大頂堆，每次取堆頂即可，但是這裡會存在一個非常尷尬的情況：如果一萬億個數中前10個剛好就是最大的，那麼這樣的話堆排序就完全在做無用功了，雖然這種情況非常少見，但是它反映了這種建大頂堆的不可取之處。

在oj題中，這種求前K個的問題，頻率還是挺高的

四：參考程式碼

Heap.h

#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <string.h>typedef int DataType;typedef struct Heap{	DataType* _arr;	int _length;	int _capacity;}Heap;void print(Heap* heap,int n);//列印void HeapInit(Heap* php, DataType* a, int n);//初始化void HeapDestroy(Heap* php);//銷燬void AdjustDown(Heap* php, int n,int root);//向下調整：前提左右子樹都是小堆void AdjustUp(Heap* php,int child);//向上調整，用於插入時void HeapCreat(Heap* php, int n);//建立堆void HeapPush(Heap* php, DataType x);//插入元素void HeapPop(Heap* php);//刪除元素，刪除頭void HeapSort(Heap* php);//堆排序DataType HeapTop(Heap* php);

Heap.c

#pragma once#include "heap.h"void print(Heap* heap,int n){	assert(heap);	for (int i = 0; i <n; i++)	{		printf("%d ", heap->_arr[i]);	}	printf("\n");}void swap(DataType* p1, DataType *p2){	DataType temp = *p2;	*p2 = *p1;	*p1 = temp;	}void AdjustDown(Heap* php, int n, int root){	int parent = root;//待交換父節點	int child = parent * 2 + 1;//預設認為左孩子小	while (child<n)//一旦child>n，parent就到了最後一層，調整完成	{		if (child+1<n && php->_arr[child + 1] > php->_arr[child])			++child;//如果右孩子比較小，就讓右孩子與父節點交換		if (php->_arr[child] > php->_arr[parent])//如果孩子小，孩子與父親交換		{			swap(&php->_arr[child], &php->_arr[parent]);			parent = child;//交換完，同時向下移動，			child = child * 2 + 1;		}		else//如果不小於，就跳出，否則會一直陷入迴圈		{			break;		}	}}void AdjustUp(Heap* php, int child)//向上調整，用於插入{	int parent = (child - 1) / 2;//求出這個孩子的父親	//while (parent>=0)//這樣寫是錯誤的，因為parent永遠都不會小於0	while(child>0)//當child>0時，早該結束了	{		if (php->_arr[child] > php->_arr[parent])		{			swap(&php->_arr[child], &php->_arr[parent]);//調整大頂堆時，如果孩子大於父親，就進行交換			child = parent;			parent = (child - 1) / 2;//與向下調整類似，只不過是向上跌打		}		else		{			break;		}	}}void HeapInit(Heap* php, DataType* a, int n){	assert(php);	php->_arr = (DataType*)malloc(sizeof(DataType)*n);	memcpy(php->_arr, a, sizeof(DataType)*n);	php->_length = n;	php->_capacity =php->_length= n;	//：從最後一個非葉結點開始，對每個結點進行向下調整}void HeapDestroy(Heap* php){	assert(php);	free(php->_arr);	php->_capacity = 0;}void HeapCreat(Heap* php, int n){	assert(php);	int i = 0;	for (i = n / 2 - 1; i >= 0; --i)//從最後一個非葉結點開始，對每個結點進行向下調整	{		AdjustDown(php, n, i);	}}void HeapSort(Heap* php){	assert(php);	for (int i = php->_capacity-1; i > 0; --i)//拿出最後一個結點放到根節點位置，然後再進行調整	{		swap(&php->_arr[0], &php->_arr[i]);		AdjustDown(php, i, 0);		print(php, php->_capacity);	}	}void HeapPush(Heap* php, DataType x)//插入元素時，只會影響一部分，所以僅對那一部分進行向上調整（）類似於並查集{	assert(php);	if (php->_length == php->_capacity)	{		php->_capacity *= 2;		DataType* temp = (DataType*)realloc(php->_arr,(sizeof(DataType))*(php->_capacity));		php->_arr = temp;	}	php->_arr[php->_length] = x;	php->_length++;	AdjustUp(php, php->_length-1);//呼叫向上調整演算法	}void HeapPop(Heap* php){	assert(php);	assert(php->_length > 0);	php->_arr[0] = php->_arr[php->_length-1];	php->_length--;	AdjustDown(php, php->_length, 0);}

test.c

#pragma once#include "heap.h"void test(){	int a[] = { 27,15,19,18,28,34,65,49,25,37 };	Heap heap;	HeapInit(&heap, a, sizeof(a) / sizeof(DataType));	print(&heap, heap._capacity);//原始	HeapCreat(&heap, heap._capacity);//建大頂堆	print(&heap, heap._capacity);	//HeapSort(&heap);//排升序	HeapPush(&heap, 97);	//HeapPush(&heap, 63);	print(&heap, heap._length);	HeapPop(&heap);	print(&heap, heap._length);}int main(){	test();}