😀大家好，我是白晨，一個不是很能熬夜😫，但是也想日更的人?，如果喜歡這篇文章，點個贊👍，關注一下👀白晨吧！你的支持就是我最大的動力！💪💪💪

在這里插入圖片描述

文章目錄

🍉前言
堆
- 🍊堆的定義及結構
- 🥝堆結構以及🥭簡單介面函式的代碼實作
- 🍎堆的創建
- - 向下調整演算法
  - 向上調整演算法
  - 堆的插入
  - 堆的洗掉
- 🍋堆的應用
- - Topk問題
  - 堆排序
- 🍍堆的全域代碼
🍓后記

🍉前言

上一篇文章，我們詳細介紹了二叉樹的入門知識（如果沒有二叉樹基礎的同學建議先看一下二叉樹入門，我在本篇文章也會對其中二叉樹中比較重要的點再次提及），在有了二叉樹的相關知識后，我們就可以著手實作一些有著更多特性的資料結構了，今天，這篇文章我們要介紹到的資料結構是一種用來排序或者找尋資料中最大、最小的若干資料的樹——堆，

堆

上一篇文章我們講到，二叉樹的順序存盤結構一般只適用于完全二叉樹，并且順序存盤結構的父子結點之間還有一些數學聯系，現在我們來回顧一下，

一棵二叉樹中最后一層結點以上結點構成滿二叉樹，且最后一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹，

在這里插入圖片描述

上圖中，第四層以上的前三層構成滿二叉樹結構，最后一層從左到右結點連續，所以上樹為一棵完全二叉樹，

完全二叉樹有如下特性：

在這里插入圖片描述

對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的陣列順序對所有結點從0開始編號，則對于序號為i的結點有：

若i>0，i位置結點的雙親序號：(i-1)/2；i=0，i為根結點編號，無雙親結點
i位置結點的孩子序號：
- 左孩子：2*i+1；
- 右孩子：2*i+2；
若2i+1=n，則無左孩子
若2i+2=n，則無右孩子

🍊堆的定義及結構

如果有一個關鍵碼的集合K = { k 0 k_0 k0?， k 1 k_1 k1? ， k 2 k_2 k2? ，…， k n ? 1 k_{n-1} kn?1? }，把它的所有元素按完全二叉樹的順序存盤方式存盤在一個一維陣列中，并滿足： k i k_{i} ki? <= k 2 i + 1 k_{2i+1} k2i+1? 且 k i k_i ki?<= k 2 i + 2 k_{2i+2} k2i+2? ( k i k_i ki? >= k 2 i + 1 k_{2i+1} k2i+1? 且 k i k_i ki? >= k 2 i + 2 k_{2i+2} k2i+2? ),i= 0，1，2…，則稱為小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，

翻譯一下就是：

如果一棵完全二叉樹樹上父節點都小于等于子節點，那么這棵完全二叉樹就被稱為小堆，

下圖為邏輯結構：

下表為存盤結構：

下標 0 1 2 3 4 5
資料 1 2 3 6 5 4

如果一棵完全二叉樹樹上父節點都大于等于子節點，那么這棵完全二叉樹就被稱為大堆，

下標 0 1 2 3 4 5
資料 6 4 5 1 2 3

從以上定義中我們可以得到堆的兩個性質：

堆一定是完全二叉樹
堆中某個節點的值總是不大于或不小于其父節點的值

特別注意：堆只要求父節點與子節點的關系，并沒有要求前一層與后一層的關系，更沒有要求存盤順序必須是有序的.

下標	0	1	2	3	4	5
資料	1	2	3	6	5	4

下標	0	1	2	3	4	5
資料	6	4	5	1	2	3

🥝堆結構以及🥭簡單介面函式的代碼實作

前面已經提過,堆的存盤結構是順序存盤,所以需要用到順序表(如果沒有順序表基礎的同學建議先去了解一下順序表<-點擊跳轉)，以下操作均會涉及到順序表的相關操作，

堆的代碼實作與順序表沒有任何區別，所以這里我們就不再贅述：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

這樣一個堆的存盤結構就搭建完畢了，現在我們來實作一下幾個簡單的介面函式，

// 堆的初始化
void HeapInit(Heap* hp);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的列印
void HeapPrint(Heap* hp);
// 取堆頂的資料
HPDataType HeapTop(Heap* hp);
// 堆的資料個數
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

堆的初始化與銷毀

由于堆的結構也是順序表，所以初始化與銷毀與銷毀與順序表沒有任何區別，我們可以直接實作，

void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp);

	free(hp->a);
	hp->capacity = 0;
	hp->size = 0;
}

堆的列印

這個操作只需要遍歷一遍堆中元素就可以，

void HeapPrint(Heap* hp)
{
	assert(hp);

	int i = 0;

	for (i = 0; i < HeapSize(hp); i++)
	{
		printf("%d ", hp->a[i]);
	}

	printf("\n");
}

取堆頂的資料

堆的堆頂元素在物理上就是順序表陣列下標為0的元素，所以我們只需要保證堆疊不為空就可以拿到這個資料，

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

堆的資料個數及堆的判空
- 堆的資料個數就是回傳堆的size大小
- 堆的判空就是判斷size是否為0，如為0，回傳真；如不為0，回傳假

int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

堆的查找

遍歷堆陣列，如果找到回傳下標，找不到回傳-1

int HeapSearch(Heap* hp, HPDataType x)
{
	assert(hp);

	for (int i = 0; i < hp->size; i++)
	{
		if (hp->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

🍎堆的創建

向下調整演算法

我們通過上面學習了解到堆對父子結點的大小關系是有一定要求的，如果現在給我們一個完全二叉樹，我們該如何將其變為大堆呢？（從這里開始，我們全都使用大堆來舉例子，小堆的情況只需要根據大堆的思想類比就可以）

先放置這個問題，我們先來看一種情況：

在這里插入圖片描述

我們可以發現這個完全二叉樹除了根結點以外，其余的結點都滿足大堆的結構，我們如何調整這個完全二叉樹可以使其成為一個大堆呢？

先讓根結點與其孩子中比較大的交換

在這里插入圖片描述

這時候我們發現，根結點已經是全部結點中最大的了，這就說明根結點已經調整好了，不用再換了，

我們現在再比較0與3這兩個結點的大小，發現0<3，不滿足大堆的要求，所以讓0與3換

在這里插入圖片描述

調整完畢，我們得到了一個小堆，

通過上面的程序，我們得到了以下經驗：

向下調整時，被調整節點的左右子樹必須都是大堆（或者小堆，根據所調整的堆而定），

如果左右子樹不是大堆，那會出現什么情況呢？

在這里插入圖片描述

這個堆的左右子樹就全不為大堆，我們現在來向下調整根結點，

根結點與較大的孩子3換

在這里插入圖片描述

由于0<5，0與5交換

在這里插入圖片描述

我們發現0結點已經調整完畢，但是這個完全二叉樹仍然不是大堆，

所以，我們可以得出結論，向下調整必須要求根結點的左右子樹為大堆(或者小堆)，

向下調整只會對二叉樹從根結點到最后調整到的位置產生影響，不會對二叉樹的全部結點產生影響

所以，我們可以根據以上程序抽象出一個向下調整的通法（大堆）：

保證要調整結點N的左右子樹都是大堆，
比較N與孩子結點的大小關系，如果N大于等于兩個孩子結點，調整結束；不然就讓N與較大的孩子交換，
重復2程序，直到N調整結束或者被調整到葉子結點，

小堆類比大堆思想就可以：

保證要調整結點N的左右子樹都是小堆，
比較N與孩子結點的大小關系，如果N小于等于兩個孩子結點，調整結束；不然就讓N與較小的孩子交換，
重復2程序，直到N調整結束或者被調整到葉子結點，

上述程序N結點始終不變，向下調整的意思就是，向下調整N結點到應在的位置

根據以上思想，我們可以實作向下調整：

// 大堆向下調整
// 向下調整結束條件
// 1. 被調整結點 >= 孩子
// 2. 調整到葉子節點
void AdjustDown_big(HPDataType* a, int n, int parent)
{
	assert(a);

	int child = parent * 2 + 1;
	//孩子必須在堆的范圍內
	while (child < n)
	{
		//選出兩個孩子中最大的進行交換，并且要保證右孩子存在
		if (a[child + 1] > a[child] && child + 1 < n)
		{
			child++;
		}

		//孩子大于父親，則交換
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}

		parent = child;
		child = parent * 2 + 1;
	}
}

// 小堆向下調整
// 向下調整結束條件
// 1. 被調整結點 <= 孩子
// 2. 調整到葉子節點
void AdjustDown_little(HPDataType* a, int n, int parent)
{
	assert(a);

	int child = parent * 2 + 1;
	//孩子必須在堆的范圍內
	while (child < n)
	{
		//選出兩個孩子中最小的進行交換，并且要保證右孩子存在
		if (a[child + 1] < a[child] && child + 1 < n)
		{
			child++;
		}

		//孩子小于父親，則交換
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}

		parent = child;
		child = parent * 2 + 1;
	}
}

這里我們假設我們堆就是滿二叉樹，向下調整一次最壞情況的時間復雜度為 O ( l o g 2 n ) O(log_2~n) O(log2? n)

我們現在回到最開始提出的問題，一個完全二叉樹怎么才能調整為一個大堆？

因為向下調整要保證左右子樹都是大堆，所以我們不可能從根結點開始調整，但是我們可以倒著調整，

在這里插入圖片描述

我們可以從倒數第一個非葉子結點開始向下調整，如上圖3結點

在這里插入圖片描述

再向下調整倒數第二個非葉子結點5

在這里插入圖片描述

3.這時根結點的左右子樹就是大堆了，我們現在來調整它

在這里插入圖片描述

調整完畢，這時我們就得到了一個大堆，

具體調整程序如下：

在這里插入圖片描述

現在我們就可以抽象出一種向下調整建堆的通法：

從最后一個非葉子結點開始向下調整，一直調整到根結點

最后，再補充一點向下建堆的時間復雜度（了解即可）

在這里插入圖片描述

向上調整演算法

在這里插入圖片描述

來看這樣一種情況，現在在一個大堆后面插入一個數9，由于9>6，所以現在構不成大堆了，要怎么調整才能將其再變為大堆呢？

由于9>6，所以我們交換6和9結點，

在這里插入圖片描述

比較8和9，8 < 9，所以根據大堆規則，交換8和9，

在這里插入圖片描述

9已經被調整到根結點，調整結束，

同樣我們可以上述程序中得到一些經驗：

被調整的結點以前的結點必須構成一個大堆
該調整也只會影響從被調整結點到最后調整到的位置的結點這一條路徑，完全二叉樹其余結點都不受影響

從以上我們可以抽象出向上調整的程序（大堆）：

保證被調整的結點N以前的結點構成一個大堆，
被調整的結點N與其父節點比較大小，如果N大于父節點，則交換這兩個結點；如果N小于等于父節點，則結束調整，
重復2程序，直到N被調整調整完畢或者調整到根結點，

小堆的向上調整類比大堆可得：

保證被調整的結點N以前的結點構成一個小堆，
被調整的結點N與其父節點比較大小，如果N小于父節點，則交換這兩個結點；如果N大于等于父節點，則結束調整，
重復2程序，直到N被調整調整完畢或者調整到根結點，

// 大堆向上調整
// 調整結束條件：
// 1.父節點 >= 被調整結點
// 2.被調整結點已經調整到根結點
void AdjustUp_big(HPDataType* a, int child)
{
	assert(a);

	while (child > 0)
	{
		int parent = (child - 1) / 2;

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
	}
}

// 小堆向上調整
// 調整結束條件：
// 1.父節點 <= 被調整結點
// 2.被調整結點已經調整到根結點
void AdjustUp_little(HPDataType* a, int child)
{
	assert(a);

	//當child為0時，結束回圈
	while (child > 0)
	{
		int parent = (child - 1) / 2;

		//孩子小于父親時交換，否則退出
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
	}
}

那么向上調整可不可以將一個完全二叉樹調整成堆呢？

答案是可以的，但是向上調整前提是被調整的結點以前的結點必須構成一個堆，所以必須要從上到下向上調整，具體要從第二個結點開始調整，保證前面的都是大堆，一直要調整到最后一個結點，

所以向上調整建堆所花費的時間要比向下調整建堆花費的時間長，一般調整一棵完全二叉樹成堆我們使用向下調整法，

向上調整的真正用處在于在堆后面插入資料，我們就要用向上調整將這個新插入的資料調整到正確的位置上，使這棵完全二叉樹再建成堆，這個用處我們后面還會提到，

堆的插入

上文提到了向上調整一般用來插入資料，現在我們就來具體探討一下堆的插入，

當堆中插入資料時，首先要判斷堆中是否已經滿了，如果滿了的話，就要擴容；
然后將資料插入到堆的最后；
最后將插入的資料向上調整，

具體代碼實作：

// 大堆資料的插入
void HeapPush_big(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->capacity == hp->size)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, newCapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("relloc fail");
			exit(-1);
		}
		hp->capacity = newCapacity;
		hp->a = tmp;
	}

	hp->a[hp->size] = x;
	AdjustUp_big(hp->a, hp->size);
	hp->size++;
}

// 小堆資料的插入
void HeapPush_little(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->capacity == hp->size)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("relloc fail");
			exit(-1);
		}
		hp->capacity = newCapacity;
		hp->a = tmp;
	}

	hp->a[hp->size] = x;
	AdjustUp_little(hp->a, hp->size);
	hp->size++;
}

代碼邏輯運行程序：

在這里插入圖片描述

堆的洗掉

堆的洗掉是指洗掉堆頂的資料，將堆頂的資料根最后一個資料一換，然后洗掉陣列最后一個資料，再進行向下調整演算法，

堆的洗掉指的是洗掉堆頂的元素，也就是說洗掉順序表陣列中下標為0的元素，

直接洗掉堆頂元素肯定行不通，因為直接洗掉這個元素會，將資料整體向前移動一位，這樣大概率會破壞堆的結構，所以我們要利用堆的特性洗掉堆疊頂元素，

我們以大堆為例，要洗掉堆疊頂元素（也就是整個堆疊中最大的元素）

我們可以將堆疊頂元素與堆疊底元素交換，然后洗掉陣列最后一個資料，這時候堆疊頂元素已經被洗掉了，
現在根結點左右子樹都是大堆，所以我們可以使用向下調整，調整根結點的位置，重新構建成堆，

小堆具體實體如下：

在這里插入圖片描述

具體代碼實作如下：

// 大堆資料的洗掉
void HeapPop_big(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_big(hp->a, hp->size, 0);
}

// 小堆資料的洗掉
void HeapPop_little(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_little(hp->a, hp->size, 0);
}

代碼邏輯運行程序：

在這里插入圖片描述

進階：

我們可以思考一個問題，堆如何實作任意洗掉？

任意洗掉其實思想仍是上述思想，我們知道移除一個元素會破壞大堆或者小堆屬性，所以我們需要將要洗掉的元素和最后一個元素交換，再向下調整原最后一個元素，

具體思路：

上文已經講述了堆的查找，所以我們要洗掉指定的元素的話，先可以使用堆的查找函式把要洗掉的元素下標找到
然后必須保證下標大于等于0，小于堆的大小
接著交換要洗掉的元素和最后一個元素，洗掉最后一個陣列資料
向下調整原最后一個元素

具體代碼實作如下：

// 大堆任意洗掉元素
void HeapDelect_big(Heap* hp,int x)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	assert(x >= 0 && x < hp->size);

	Swap(&hp->a[x], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_big(hp->a, hp->size, x);
}

// 小堆任意洗掉元素
void HeapDelect_little(Heap* hp,int x)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	assert(x >= 0 && x < hp->size);

	Swap(&hp->a[x], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_little(hp->a, hp->size, x);
}

其實上面的任意洗掉函式仍然有優化的空間，因為下標是隨著堆的結構變化不停變動的，所以使用一次洗掉前就必須查找一次，

但是我們如果可以改進查找函式，使其回傳對應位置的指標，在洗掉時，傳遞指標，找到此資料進行洗掉，此功能較好實作，大家可以自己試一試將其實作，

最后，堆的洗掉大部分都是洗掉堆頂元素，所以任意洗掉不是必須要掌握，大家做一了解即可，

🍋堆的應用

我們已經了解了堆的結構、特性和常用的介面函式，現在就可以將其應用到日常的問題中，堆最常用的應用一般有兩個——Topk問題和堆排序，

Topk問題

Topk問題指的是選出一株資料中最大或者最小的幾個，

如，王者榮耀中英雄的國服最強，考試成績的全校前十等

如果給我們一組資料，如果要讓我們選出最大的10個數，那么我們可能有以下思路：

在這里插入圖片描述

方式2到方式1的時間復雜度小了很多，但是這兩個方法都有一個致命的缺陷——空間復雜度為 O ( N ) O(N) O(N)，

我們來假設一種場景，如果我們有10億個資料，記憶體中無法存盤這么多資料，那應該怎么辦呢？

有機智的小伙伴可能就會說用外部排序不就可以給磁盤中的資料排序了嗎？這是一種可行的方法，但是如果為了找10個資料就要排序全部的資料，時間成本和消耗都太大，得不償失，

所以，現在就是體現我們堆結構優越性的地方了，我們可以得到第三種方式：

在這里插入圖片描述

首先解釋為什么要建小堆，如果要排最大幾個數，一般思路應該是建大堆，但是大堆有個致命的缺點，大堆堆頂元素是最大的元素，如果剛好最大的元素在前k個數中，那么直接就會堵死堆，應該用什么方法判斷一個資料是否是最大的幾個數（是否能進堆）呢？
當然不能與堆中的全部元素比較，這樣時間復雜度太高，所以我們可以先建一個大小為k的小堆，這樣堆頂資料就是堆中資料中最小的資料，其余的資料只要大于堆疊頂的資料就可以進堆，然后再向下調整，使堆中最小的資料再次回到堆頂，
這里我們可以感性認識一下，小堆可以讓小的資料占據堆頂，而讓大的資料向下滑，所以不會堵死堆，
最后比較完全部的數，堆里的數就是最大的k個數，

選出最小的數也是一個道理：

用前k個數建一個大堆（最大的數在堆頂）
用剩下的數與堆疊頂資料比較，如果小于這個數就替換堆頂的數，再向下調整，使堆中最大的數始終在堆頂
比較結束后，堆中的k個數就是最小的k個數

特別提醒：這種方法只是選出最大或者最小的前k個數，并不會給這k個數排序，

具體代碼實作如下：

// 找出最大的前k個數
void PrintTopK(int* a, int n, int k)
{
	assert(a);
	
	// 建小堆
	Heap hp;
	HeapInit(&hp);

	for (int i = 0; i < k; i++)
	{
		HeapPush_little(&hp, a[i]);
	}
	
	// 堆頂元素與其余元素比較
	for (int i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			hp.a[0] = a[i];
			AdjustDown_little(hp.a, hp.size, 0);
		}
	}

	HeapPrint(&hp);

	HeapDestory(&hp);
}

// 找出最小的前k個數
void PrintTopK(int* a, int n, int k)
{
	assert(a);
	
	// 建大堆
	Heap hp;
	HeapInit(&hp);

	for (int i = 0; i < k; i++)
	{
		HeapPush_big(&hp, a[i]);
	}
	
	// 堆頂元素與其余元素比較
	for (int i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			hp.a[0] = a[i];
			AdjustDown_big(hp.a, hp.size, 0);
		}
	}

	HeapPrint(&hp);

	HeapDestory(&hp);
}

堆排序

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序演算法，堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點，

所以說堆排序就是利用堆的性質完成排序的程序，堆排序主要妙就妙在它的思想上，這里我們直接來看堆排序的思想：

總共分為兩個步驟：

建堆

升序：建大堆
降序：建小堆

利用堆洗掉思想來進行排序

建堆和堆洗掉中都用到了向下調整，因此掌握了向下調整，就可以完成堆排序，

具體解釋（升序）：

升序就是從小到大排列，正常思維應該是建小堆，可是建小堆無法保證除了堆頂元素其余元素的順序，所以我們要反其道而行之，我們先建大堆，堆頂元素就是最大的元素，
然后利用堆洗掉的思想，交換堆頂和堆底的元素，然后將堆的大小減小1個資料，這時候最大的元素就被換到了最后，再向下調整現在的堆疊頂元素，
重復程序2，直到剩堆中只剩一個元素，就完成了堆排序，

降序的思想也與升序相似：

降序就是從大到小排列，正常思維應該是建大堆，可是建大堆無法保證除了堆頂元素其余元素的順序，所以我們要反其道而行之，我們先建小堆，堆頂元素就是最小的元素，
然后利用堆洗掉的思想，交換堆頂和堆底的元素，然后將堆的大小減小1個資料，這時候最小的元素就被換到了最后，再向下調整現在的堆疊頂元素，
重復程序2，直到剩堆中只剩一個元素，就完成了堆排序，

具體實體圖解如下：

在這里插入圖片描述

堆排序動態的邏輯程序：

在這里插入圖片描述

具體代碼實作：

// 堆排序升序
void HeapSortUp(HPDataType* a, int n)
{
	assert(a);

	// 向下調整建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown_big(a, n, i);
	}

	// 將最后一個元素與堆頂元素交換，選出最大的元素，堆大小減一，然后向下調整，選出此大的元素，以此類推
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown_big(a, i, 0);
	}
}

// 堆排序降序
void HeapSortDown(HPDataType* a, int n)
{
	assert(a);

	// 向下調整建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown_little(a, n, i);
	}

	// 將最后一個元素與堆頂元素交換，選出最小的元素，堆大小減一，然后向下調整，選出此大的元素，以此類推
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown_little(a, i, 0);
	}
}

代碼邏輯動態展示：

在這里插入圖片描述

🍍堆的全域代碼

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

// 堆的構建
void HeapInit(Heap* hp);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 向上調整
void AdjustUp_big(HPDataType* a, int child);
void AdjustUp_little(HPDataType* a, int child);
// 堆的插入
void HeapPush_big(Heap* hp, HPDataType x);
void HeapPush_little(Heap* hp, HPDataType x);
// 堆的列印
void HeapPrint(Heap* hp);
// 堆的洗掉
void HeapPop_big(Heap* hp);
void HeapPop_little(Heap* hp);
// 取堆頂的資料
HPDataType HeapTop(Heap* hp);
// 堆的資料個數
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
// 堆的查找
int HeapSearch(Heap* hp, HPDataType x);
// 堆的任意洗掉
void HeapDelect_big(Heap* hp, int x);
void HeapDelect_little(Heap* hp, int x);

// TopK問題：找出N個數里面最大/最小的前K個問題，
// 需要注意：
// 找最大的前K個，建立K個數的小堆
// 找最小的前K個，建立K個數的大堆
void PrintTopK(int* a, int n, int k);

// 對陣列進行堆排序
void HeapSortUp(HPDataType* a, int n);
void HeapSortDown(HPDataType* a, int n);


void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp);

	free(hp->a);
	hp->capacity = 0;
	hp->size = 0;
}

bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

void HeapPrint(Heap* hp)
{
	assert(hp);

	int i = 0;

	for (i = 0; i < HeapSize(hp); i++)
	{
		printf("%d ", hp->a[i]);
	}

	printf("\n");
}

void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustUp_big(HPDataType* a, int child)
{
	assert(a);

	while (child > 0)
	{
		int parent = (child - 1) / 2;

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
	}
}

void AdjustUp_little(HPDataType* a, int child)
{
	assert(a);

	//當child為0時，結束回圈
	while (child > 0)
	{
		int parent = (child - 1) / 2;

		//孩子小于父親時交換，否則退出
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
	}
}

void HeapPush_big(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->capacity == hp->size)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, newCapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("relloc fail");
			exit(-1);
		}
		hp->capacity = newCapacity;
		hp->a = tmp;
	}

	hp->a[hp->size] = x;
	AdjustUp_big(hp->a, hp->size);
	hp->size++;
}

void HeapPush_little(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->capacity == hp->size)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("relloc fail");
			exit(-1);
		}
		hp->capacity = newCapacity;
		hp->a = tmp;
	}

	hp->a[hp->size] = x;
	AdjustUp_little(hp->a, hp->size);
	hp->size++;
}

void AdjustDown_big(HPDataType* a, int n, int parent)
{
	assert(a);

	int child = parent * 2 + 1;
	//孩子必須在堆的范圍內
	while (child < n)
	{
		//選出兩個孩子中最大的進行交換，并且要保證右孩子存在
		if (a[child + 1] > a[child] && child + 1 < n)
		{
			child++;
		}

		//孩子大于父親，則交換
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}

		parent = child;
		child = parent * 2 + 1;
	}
}

void AdjustDown_little(HPDataType* a, int n, int parent)
{
	assert(a);

	int child = parent * 2 + 1;
	//孩子必須在堆的范圍內
	while (child < n)
	{
		//選出兩個孩子中最小的進行交換，并且要保證右孩子存在
		if (a[child + 1] < a[child] && child + 1 < n)
		{
			child++;
		}

		//孩子小于父親，則交換
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}

		parent = child;
		child = parent * 2 + 1;
	}
}

void HeapPop_big(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_big(hp->a, hp->size, 0);
}

void HeapPop_little(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_little(hp->a, hp->size, 0);
}

int HeapSearch(Heap* hp, HPDataType x)
{
	assert(hp);

	for (int i = 0; i < hp->size; i++)
	{
		if (hp->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

void PrintTopK(int* a, int n, int k)
{
	assert(a);

	Heap hp;
	HeapInit(&hp);

	for (int i = 0; i < k; i++)
	{
		HeapPush_little(&hp, a[i]);
	}
	
	for (int i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			hp.a[0] = a[i];
			AdjustDown_little(hp.a, hp.size, 0);
		}
	}

	HeapPrint(&hp);

	HeapDestory(&hp);
}

void HeapSortUp(HPDataType* a, int n)
{
	assert(a);

	// 向下調整建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown_big(a, n, i);
	}

	// 將最后一個元素與堆頂元素交換，選出最大的元素，堆大小減一，然后向下調整，選出此大的元素，以此類推
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown_big(a, i, 0);
	}
}

void HeapSortDown(HPDataType* a, int n)
{
	assert(a);

	// 向下調整建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown_little(a, n, i);
	}

	// 將最后一個元素與堆頂元素交換，選出最小的元素，堆大小減一，然后向下調整，選出此大的元素，以此類推
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown_little(a, i, 0);
	}
}

void HeapDelect_big(Heap* hp,int x)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	assert(x >= 0 && x < hp->size);

	Swap(&hp->a[x], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_big(hp->a, hp->size, x);
}

void HeapDelect_little(Heap* hp,int x)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	assert(x >= 0 && x < hp->size);

	Swap(&hp->a[x], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown_little(hp->a, hp->size, x);
}

🍓后記

恭喜呀🎉！你已經掌握了堆的全部用法了🎊！！距離大佬又近了一步🎇！！！

寫這篇文章對白晨來說也是一種挑戰，特別是堆的精華部分——向下調整演算法和向上調整演算法，希望大家看的還算清楚明白，

白晨會不斷提高自己的制圖水平和語言描述能力，希望能讓每個人都看得清楚明白😋，大家有什么想法都可以私信白晨呀，無論是提意見還是交朋友，白晨都會一一回復的🥳，

最后如果大家喜歡我這篇文章，不如給我一個大拇指 👍和小星星 ??，支持一下白晨吧！喜歡白晨《資料結構》系列的話，不如關注👀白晨，以便看到最新更新喲！！！

我是不太能熬夜的白晨，我們下篇文章見，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/413414.html

標籤：java

上一篇：LeetCode 二叉樹相關Easy題 --- 二叉樹

下一篇：IntelliJ IDEA中的神仙插件（寫代碼必備）

【資料結構】堆的全決議

文章目錄

🍉前言

堆

🍊堆的定義及結構

🥝堆結構以及🥭簡單介面函式的代碼實作

🍎堆的創建

向下調整演算法

向上調整演算法

堆的插入

堆的洗掉

🍋堆的應用

Topk問題

堆排序

🍍堆的全域代碼

🍓后記