目錄

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

1.1 概念（概念總是重要的）

1.2 結(jié)構(gòu)，分為兩種

1.2.1 小堆/小根堆示例

1.2.2 大堆/大根堆示例

2、堆的接口

3、接口實(shí)現(xiàn)

3.1 堆的初始化

3.2 堆的銷(xiāo)毀

3.3 堆的插入

功能分析：

功能實(shí)現(xiàn)：

3.4 堆的刪除

功能分析：

功能實(shí)現(xiàn)：

3.5 取堆頂?shù)臄?shù)據(jù)

3.6 堆的數(shù)據(jù)個(gè)數(shù)

3.7 堆的判空

4、完整代碼

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

1.1 概念（概念總是重要的）

上面這一段是堆的概念，但是這也太沒(méi)勁了吧，我們來(lái)通俗的講一下，敲黑板了嗷：

堆的本質(zhì)是一個(gè)完全二叉樹(shù)。

大堆（也叫大根堆）：父節(jié)點(diǎn)大于/等于子節(jié)點(diǎn)。

小對(duì)（也叫小根堆）：父節(jié)點(diǎn)小于/等于子節(jié)點(diǎn)。

如果不滿足上面的條件，那么就不是堆。

堆的性質(zhì)：

1、堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
2、堆總是一棵完全二叉樹(shù)。

1.2 結(jié)構(gòu)，分為兩種

1.2.1 小堆/小根堆示例

1.2.2 大堆/大根堆示例

我們來(lái)看一個(gè)題目：

下列關(guān)鍵字序列為堆的是：（A）

A 100,60,70,50,32,65

B 60,70,65,50,32,100

C 65,100,70,32,50,60

D 70,65,100,32,50,60

E 32,50,100,70,65,60

F 50,100,70,65,60,32

分析：我們畫(huà)圖來(lái)分析

2、堆的接口

本篇文章是以小堆為例來(lái)實(shí)現(xiàn)的。堆的數(shù)據(jù)存儲(chǔ)是用數(shù)組存的，數(shù)據(jù)的內(nèi)存中的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)的，我們?yōu)榱撕美斫?，以邏輯結(jié)構(gòu)理解的。

堆的接口有：初始化、銷(xiāo)毀、插入、刪除、取堆頂、堆的數(shù)據(jù)個(gè)數(shù)、判空。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

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

// 堆的初始化
void HeapInit(Heap* hp);
// 堆的銷(xiāo)毀
void HeapDestory(Heap* hp);
//交換
void Swap(HPDataType* p1, HPDataType* p2);
//向上調(diào)整
void AdjustUp(HPDataType* a, int child);
//向下調(diào)整
void AdjustDown(HPDataType* a, int size, int parent);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(Heap* hp);
// 堆的數(shù)據(jù)個(gè)數(shù)
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

3、接口實(shí)現(xiàn)

我們這些接口好多都是與之前的數(shù)據(jù)結(jié)構(gòu)文章是類(lèi)似的，前面已經(jīng)多次講解，這里就不再講解了，要是有看不懂的地方可以參考之前的數(shù)據(jù)結(jié)構(gòu)文章。

3.1 堆的初始化

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

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

3.2 堆的銷(xiāo)毀

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

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

3.3 堆的插入

堆的插入是比較復(fù)雜的，也是一個(gè)難點(diǎn)，我們先來(lái)分析，再去實(shí)現(xiàn)功能。

功能分析：

1、插入的時(shí)候我們先要看數(shù)組是否需要擴(kuò)容，先判滿，如果空間滿了就先擴(kuò)容，然后將新元素插入到數(shù)組的尾部；

2、我們新插入一個(gè)元素，就需要去分析一下此堆是否滿足小堆的結(jié)構(gòu)，如果不滿足我們就需要將新元素向上調(diào)整。

3、向上調(diào)整過(guò)程分析：

我們來(lái)舉例分析一下：如果給一個(gè)小堆插入一個(gè)元素后，堆的結(jié)構(gòu)被破壞，如何調(diào)整才能恢復(fù)小堆的結(jié)構(gòu)。

a、當(dāng)我們發(fā)現(xiàn)給小堆插入一個(gè) 10 后，10 比父節(jié)點(diǎn) 28 小，破壞了小堆的結(jié)構(gòu)，我們需要對(duì)堆進(jìn)行調(diào)整；

b、堆的物理結(jié)構(gòu)是數(shù)組，所以我們可以通過(guò)下標(biāo)來(lái)找到父節(jié)點(diǎn)，這里找父節(jié)點(diǎn)的公式：parent = (child-1)/2。當(dāng)我們找到父節(jié)點(diǎn)后，讓子節(jié)點(diǎn)與父節(jié)點(diǎn)去比較，如果小于父節(jié)點(diǎn)我們就讓兩個(gè)節(jié)點(diǎn)的元素交換，交換后的父節(jié)點(diǎn)與它的父節(jié)點(diǎn)可能也不滿足小堆，因此需要不斷的向上調(diào)整；

c、循環(huán)去比較調(diào)整，當(dāng)child = 0 時(shí)，我們的調(diào)整就結(jié)束了，因此我們的循環(huán)判斷條件為 child > 0。

注意：當(dāng)有一次調(diào)整完后，我們的堆已經(jīng)成為了小堆，就跳出循環(huán)。

我們根據(jù)上面的思路來(lái)畫(huà)圖走一遍：

我們對(duì)功能的分析就結(jié)束了，開(kāi)始實(shí)現(xiàn)功能。

功能實(shí)現(xiàn)：

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])//這里控制大小堆
		{
			Swap(&a[child], &a[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//log N 
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

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

		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

	AdjustUp(hp->a, hp->size - 1);
}

交換與向上調(diào)整后面我們會(huì)復(fù)用的，因此我們將其兩個(gè)功能封裝成函數(shù)。

3.4 堆的刪除

堆的刪除是刪堆頂?shù)脑亍?/strong>

思路：堆頂數(shù)據(jù)與最后一個(gè)數(shù)據(jù)交換，刪掉最后一個(gè)數(shù)據(jù)，再?gòu)亩秧斚蛳抡{(diào)整。

void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)//當(dāng)child大于了數(shù)組大小就跳出循環(huán)
	{
		//找出左右孩子中小/大的那個(gè)（假設(shè)法）
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//log N
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

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

	AdjustDown(hp->a, hp->size, 0);
}

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

	return hp->a[0];
}

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

	return hp->size;
}

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

	return hp->size == 0;
}