1.構(gòu)建堆

首先，儲存堆我們用到的是數(shù)組，我們把它封裝為一個結(jié)構(gòu)體

typedef int HDataType;

typedef struct Heap
{
	HDataType* arr;
	int size;
	int capacity;
}Heap;

size是數(shù)組里面有效數(shù)據(jù)的個數(shù)，capacity是數(shù)組的容量大小。

雖然堆在物理結(jié)構(gòu)上是一個數(shù)組，但在邏輯結(jié)構(gòu)上我們把它想象做一個完全二叉樹，如下圖

這樣我們可以通過下標來訪問這棵樹。
下面是通過父親訪問孩子：
我們定義父節(jié)點的下標為parent，那左孩子節(jié)點的下標就是parent * 2 + 1，右孩子節(jié)點的下標是parent * 2 + 2，比如上圖中的26 下標是1，1 * 2 + 1是下標為3的左孩子36。
下面是通過孩子訪問父親：
定義孩子下標為child,如果child是左孩子，那么(child - 1) / 2就可以得到父節(jié)點的下標，如果child是右孩子的話，本來我們應(yīng)該是(child - 2) / 2，因為如果減一除二的話可能會得到一個小數(shù)，比如(4 - 1) / 2 = 1.5,但這是我們數(shù)學(xué)上的算法，在C語言里，整數(shù)除法是向下取整的，因此結(jié)果還是1，不是1.5，所以無論是左右孩子我們都可以減一除二得到父節(jié)點的下標。

另外，堆分為大堆和小堆，大堆滿足父節(jié)點的數(shù)不小于子節(jié)點，小堆滿足父節(jié)點不大于子節(jié)點。

1.1 向下調(diào)整算法

要想構(gòu)建一個堆，我們得先學(xué)習(xí)向下調(diào)整算法，假設(shè)我們現(xiàn)在有一個堆，左子樹和右子樹都是小堆，只有堆頂不滿足小堆的性質(zhì)，比如這棵樹

我們只需要把堆頂?shù)臄?shù)據(jù)調(diào)到合適的位置，它就是一個小堆了，我們可以這樣做：先找出堆頂?shù)淖笥液⒆又行〉哪且粋€，再讓它和堆頂數(shù)據(jù)比較，如果孩子小，就讓它和父節(jié)點進行交換，比如這里的29是父節(jié)點，它的左右孩子是26和16，其中小的是16，然后16和29比，孩子小，就讓16和29進行交換

此時我們交換的是右孩子和父節(jié)點，左邊沒有動過，因此左邊依然是小堆，我們只需要改右邊就可以了，現(xiàn)在新的29是我們下一個要進行比較的父節(jié)點，找出它的左右孩子中小的那一個，當(dāng)然這里只有左孩子20，比較得父節(jié)點大，再交換左孩子和父節(jié)點

此時，我們已經(jīng)成功得到了一個小堆。
下面是代碼實現(xiàn)（建小堆，如果要建大堆改掉一些小于號就可以），參數(shù)中arr是要調(diào)整的數(shù)組，n是數(shù)組的大小，root是堆頂?shù)南聵?/p>

void AdjustDown(HDataType* arr, int n, int root)
{
	int parent = root;
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1]) //child + 1 < n 防止越界
		{
			child = child + 1;
		}
		//到這child下標是兩個孩子中小的呢個的下標
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
		}
		else 
		{
			break;
		}
		parent = child;
		child = 2 * parent + 1;
	}
}

但這樣調(diào)整只適合左子樹和右子樹都已經(jīng)是堆的情況啊，那一般的情況又怎么辦呢？
其實，一棵樹的每個葉節(jié)點可以看做只有它自己的一個堆，因為只有自己，所以它已經(jīng)滿足堆的條件

比如這里的52,11,35,15,73。
如果我們對29進行向下調(diào)整算法，算法就會把29調(diào)到合適的位置，使得這個堆變成小堆，調(diào)完之后我們再調(diào)27，又可以把這個堆調(diào)成小堆，接下來繼續(xù)往回走，再調(diào)46，直到把所有父節(jié)點都調(diào)完，整個堆就變成了小堆。
因為我們是用數(shù)組維護的堆，所以上面這個遍歷父節(jié)點的過程我們可以通過下標減1來遍歷。那怎么找到第一個父節(jié)點29呢，前面我們提到了size是數(shù)組里有效數(shù)據(jù)的個數(shù)，所以最后一個數(shù)據(jù)的下標就是size - 1，（size - 1）/ 2就是最后一個父節(jié)點的下標。

下面是利用向下調(diào)整建堆的代碼

	for (int i = (size -1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, size, i);
	}

我們構(gòu)建堆一般是放在堆的初始化函數(shù)里面的，堆的初始化一般就是給你一個數(shù)組，把數(shù)組里面的元素弄成堆。
ph是我們堆的結(jié)構(gòu)體指針，使用前記得先創(chuàng)建一個結(jié)構(gòu)體變量，這里是把它的地址傳進去，s是我們要修改成堆的數(shù)組，n是數(shù)組的大小

void HeapInit(Heap* ph, HDataType* s, int n)
{
	ph->arr = (HDataType*)malloc(sizeof(HDataType) * n);
	memcpy(ph->arr, s, sizeof(HDataType) * n);//把s里面的數(shù)據(jù)復(fù)制到我們的數(shù)組里面
	ph->capacity = ph->size = n;

	//構(gòu)建堆
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		AdjustDown(ph->arr, n, i);
	}
}

1.2 構(gòu)建堆的時間復(fù)雜度分析

分析建堆的時間復(fù)雜度就是看它運行了多少次，向下調(diào)整算法每次需要移動樹的高度-1次，設(shè)高度為h
建堆的時間復(fù)雜度就是每一層的節(jié)點個數(shù)乘以移動的次數(shù)，再把每一層相加，設(shè)和為S，即

求這個和我們用到錯位相減法
同時，h = logN（默認以2為底），所以時間復(fù)雜度為O(N - logN)，因為logN很小，所以也就是O(N)。

2.堆排序

2.1 堆排序的實現(xiàn)

堆排序就是用堆這個數(shù)據(jù)結(jié)構(gòu)來對一些數(shù)據(jù)進行排序，如果我們有一個小堆，那么堆頂?shù)臄?shù)就是最小的數(shù)，我們需要再找一個次小的數(shù)，該怎么找呢？
我們可以這樣做：把堆頂?shù)臄?shù)和數(shù)組中最后一個數(shù)互換，然后把數(shù)組長度減1，認為最后一個數(shù)不是數(shù)組里面的，這樣再對新的堆頂進行向下調(diào)整構(gòu)建新的堆，這個時候的堆頂就是次小的數(shù)，再重復(fù)之前的操作，直到數(shù)組里只有一個數(shù)據(jù)，這個時候數(shù)組里面的數(shù)據(jù)就排好序了。
需要注意，這種排序 建大堆排升序，建小堆排降序。
代碼實現(xiàn)：

void HeapSort(HDataType* arr,int n)
{
	//構(gòu)建堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
	//開始排序
	int end = n - 1;   //數(shù)組最后一個數(shù)的下標
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

2.2 堆排序的時間復(fù)雜度

堆排序的執(zhí)行次數(shù)是數(shù)據(jù)個數(shù)乘以向下調(diào)整的時間復(fù)雜度，即
O(N * logN)，就算加上建堆的時間復(fù)雜度O(N),N 和 N * logN相比，N也比較小，所以直接取O(N * logN)。

3. TOP-K問題

這類問題是給出N個數(shù)，求出最?。ㄗ畲螅┑那癒個數(shù)，或者是第K?。ù螅┑臄?shù)。
這中問題用堆可以很好地解決，我們用N個數(shù)中的前K個數(shù)構(gòu)建一個大小為K的堆，如果要最大的前K個數(shù)，就建小堆，然后再讓堆頂?shù)臄?shù)和剩下的N-K個數(shù)一一比較，如果堆頂?shù)臄?shù)小，就把堆頂?shù)臄?shù)換成大的，再繼續(xù)比較，最終堆里面的K個數(shù)就是最大的前K個數(shù)。
這種方法優(yōu)點是可以解決數(shù)據(jù)太多內(nèi)存放不下的問題，同時時間復(fù)雜度很小，為O(N*logK)。文章來源地址http://www.zghlxwxcb.cn/news/detail-827888.html

到了這里，關(guān)于詳解數(shù)據(jù)結(jié)構(gòu)中的堆的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！