前言

堆的性質：堆中某個節點的值總是不大于或不小于其父節點的值；堆總是一棵完全二叉樹，
注意區分，二叉樹的堆是一種資料結構，而系統層的堆是作業系統中管理記憶體的一塊區域分段，不要弄混淆了，

一、預備小知識

觀察上圖我們能夠得到以下幾個結論：
第一個：順序表作為堆的儲存結構的是比較合適的，因為這樣子我們用的順序表就可以不會存在空間的浪費，比如前面出現NULL之類的，所以我們用順序表作為堆的儲存結構，它的邏輯結構是一顆滿二叉樹，并且作為堆還要滿足每個父親大于孩子或者每個父親都小于孩子
第二個：每個節點它的左孩子若是存在，左孩子的下標就一定是（父親的下標*2+1），而每個孩子它的父親則是（父親的下標 =（孩子的下標-1）/2），也就是我們這里的結論能夠找到當前節點的孩子節點和父親節點，

二、建堆

1.初始化堆（小堆為例）

假設給定一個陣列，我們去初始化堆，這里是有兩種方法
給定陣列：int array[] = {27,15,19,18,28,34,65,49,25,37};

方法一：倘若我們的堆已經像上圖一樣，根的左子樹和右子樹都已經是一個小堆了，我們如何通過演算法來使他變成一個小堆
向下調整演算法：當一個節點的左右子樹都是堆的時候適用
觀察我們要調整27的話，我們27的每一次變動都會影響到左右子樹，所以我們要保證不影響左右子樹的堆性質的同時改變它的儲存結構，方法也就是將它的左孩子和右孩子當中挑選小的，和根進行交換，這時對于其中的一邊子樹，如圖中的19一路，當15與27交換的時候，實際上不改變19這個子樹的堆的性質，但是對于15的子樹我們換了一個更大的數，而我們建的是小堆，所以對于15的這顆子樹，我們也要像處理27的邏輯一樣，直到出現交換到了根節點或者父節點比左右孩子都小，

//向下調整演算法,a為底層結構的陣列，n為調整的陣列的大小，parent為調整的節點
void AdjustDown(int* a,int n ,int parent)
{
	//適合左右都是堆，parent不滿足的情況的排序
	//每一個parent都有可能要交換到葉子
	int child = parent * 2 + 1;
	//排序的節點一定會有左孩子
	while (child<n)
	{
		//小堆為例
		if (child + 1 < n && a[child] > a[child + 1])
			child++;
		if (a[child] < a[parent])
			Swap(&a[child], &a[parent]);
		else//表示父親比最小孩子的孩子小，滿足堆
		break;
		//走到這里，表示進行了交換，還要繼續往下走
		parent = child;
		child = parent * 2 + 1;
	}
}

走到這里，我們僅僅只是處理了當左右子樹都是小根堆的情況，那如果不滿足的時候我們該怎么解決呢，如下圖：
這個時候其實我們可以看到從索引為2的地方（即最后一個父節點，索引為最順序表中最后一個數的下標(n - 1 - 1) / 2）其中n 為陣列的大小，它的左子樹和右子樹都只有一個數，那么也是可以認為是一個左右子樹都已經是堆的結構，我們就可以從索引為2倒著更新 2 --> 1 --> 0,當我們走到0的時候，0的左右子樹就都是小根堆了，這樣子我們就可以用向下調整演算法弄出一個小根堆

代碼如下：

void HeapSort(int* a, int n)
{
	//我們從最后一個父節點開始建堆，從后向前遍歷
	//這樣就能保證都是小堆
	//對節點用向下調整就可以了，這里我們建小堆

	//這里的 n-1是最后一個數的索引， (n-1-1)/2是他的父親索引！
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		//i表示我們傳參的父節點
		AdjustDown(a, n, i);
	}
}

走到這里第一種初始化堆的方式說完啦！！！
int arr[] ={20,30,60,25,27,55,57};
接著第二種：向下調整演算法可以做到初始化堆，向上調整演算法其實也是可以的，其實這里與之后講的根的插入的思想類似,也就是當我們陣列只有20的時候我們通過插入30來保證是一個小堆，然后插入60保證是一個小堆（圖一：可以發現都不用調整）
我們再繼續插入25又會如何呢（下圖），可以發現當我們插入時不滿足30是一個小堆，所以我們將30 與 25 交換，這樣原來的1號索引的樹就是一個小堆了，但對于1號索引的父親，我們將一個比1號索引小的數（25）放到1號位置，我們這個時候其實還是要進行1號位和他的父親（0號位），倘若0號位比1號位小，則結束，不然就交換，迭代到根，也結束！！ 所以向上調整演算法的思想也比較簡單，也就是迭代到滿足條件即可
向上調整的代碼：

void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//再進行迭代
			child = parent;
			//注意parent在這里不可能會是負數
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

2.證明建堆的復雜度

當我們是用向下調整演算法來建堆的話吧
畫的有點丑，但是意思就是從最后一個父節點更新節點*它的更新層數

三、堆的插入

堆的插入其實可以先將資料放在順序表的尾，然后再通過一次向上調整演算法就可以實作一次堆的插入，如原資料{1,2，3}后面插入0

代碼：

void HeapPush(Heap* hp, HPDataType x)
{
	//插入一個數在陣列的末尾，在用向上調整演算法（只影響一條路徑）
	//注意考慮增容
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		int newcpacity = hp->_capacity * 2;
		HPDataType*tmp = realloc(hp->_a, newcpacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->_a = tmp;
		hp->_capacity = newcpacity;
	}
	//走到這里，空間都是足夠的
	hp->_a[hp->_size++] = x;
	AdjustUp(hp->_a, hp->_size-1);
}

插入資料前需要檢測容量，然后放在陣列尾，++size，再用向上調整演算法即可，

四、堆的洗掉

堆的洗掉一般是洗掉頭的資料，因為這樣子能夠少的破壞左右子樹堆的結構，
不然的話洗掉資料之后又需要重新建堆O（N），這樣子的洗掉效率效率太低了，我們可以將頭和尾的資料進行交換，size–之后再對頭進行向下調整演算法，這時候剛好因為沒破壞左右子樹是堆所以可以使用

void HeapPop(Heap* hp)
{
	//洗掉一個資料可以讓第一個資料和最后一個資料交換
	//hp的size--之后就可以對第一個數進行向下調整演算法
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->_a[--hp->_size], &hp->_a[0]);

	AdjustDown(hp->_a, hp->_size, 0);
}

五、TopK問題

現在我們需要從（N）10億個整數當中挑選最大的（K）10個，怎么做？
首先解釋一下為什么挑選最大的10個數要建小堆，如果建大堆，最大的數可能擋在頭的位置，其他9個次大的數就進不來，所以建小堆就可以將最大的數更新進堆中！
1.首先這里有4g的位元組，如果需要排序的話放到記憶體當中排可能會因為記憶體不夠排放不了，加入能排那我們的時間復雜度也是O（NlogN），
2.其次我們可以考慮建堆，如果正常思路建堆：即建一個10億個數的小堆，實際記憶體也存不下，假設存的下的話，建堆的時間復雜度是O(N)，K個數選出來是O（KlogN），總共時間復雜度O(N+KlogN)–>10億加300，效率比起排序還是會好一些的，那么還有沒有更好的方法呢?
3. 還是建堆，我們建一個10個數的小堆，將（10億-10）個數依次放入堆中，建堆的時間復雜度O(K)，找到K個數的時間復雜度（NlogK），時間復雜度就是O(K+NlogK)–>10+40億，但是空間只開了O（K）個，當K小的時候，是十分優秀的了！
結論：乍一看，第二種的時間復雜度可能還會好一些，實際上和第三種都是在一個量級的，實際上當我們N為100億的時候都已經不可能建堆了，因為它的空間復雜度為O(N)，而我們的第三種方法的空間復雜度為O(K)，所以在時間復雜度差不多的情況下，對于空間消耗的topK的解法實際上更受到我們歡迎！

void PrintTopK(int* a, int n, int k)
{
	//假設從N個數當中挑選最大的K個
	//拿前k個數初始化，當我們要挑選最大的前K個數的時候
	//我們選擇建小堆，這樣才不會被最大的數擋在a[0]這個位置
	//先對開始的陣列進行建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}
	for (int i = k; i < n; ++i)
	{
		//遍歷下標【k ，n-1】的數，依次在我們的堆里面比較
		//當有一個數比我們的堆頂大的時候我們就覆寫就可以
		if (a[0] < a[i])
		{
			a[0] = a[i];
			AdjustDown(a, k, 0);
		}
	}
}
void TestTopk()
{
	int* a=(int*)malloc(sizeof(int)*100000);
	srand(0);
	//創建100000（N）亂數并且都小于10000
	for (int i = 0; i < 100000; i++)
	{
		a[i] = rand()%10000;
	}
	//創建隨機十個位置（K）大于10000，觀察程式能否找到
	a[1024] = 10001;
	a[10240] = 10002;
	a[10204] = 10003;
	a[10024] = 10005;
	a[10125] = 100000;
	a[10224] = 10004;
	a[10234] = 1000100;
	a[10214] = 10006;
	a[15044] = 10009000;
	a[15045] = 10009001;
	PrintTopK(a, 100000, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

實際上在我們后面學習c++的時候接觸到仿函式的時候，我們可以通過傳參的方式來確認我們建的是大堆還是小堆，priority_queue的底層就是一個堆，當然他可以用我們這里的順序表vector,也可用deque雙端佇列來實作，

全部代碼

碼云

總結

堆的就到此結束啦，之后在C++的優先級佇列當中會用到這里的知識，到時候的實作實際上也是差不多的，有幫助的一鍵三連吧！！！