系列文章目錄

前言

一、堆的概念

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

二、堆的性質

1. 堆中某個節點的值總是不大于或不小于其父節點的值；
2. 堆總是一棵完全二叉樹，
3. 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹，
4. 完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，通俗來說k-1的深度時樹都是滿的，最后一層k的深度可以不滿，但從左到右是連續的，
   
   

三、堆的實作

1.用陣列定義堆結構struct Heap

代碼如下：

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

2.交換兩個數Swap函式

代碼如下：

void Swap(int* left, int* right)
{
	int tmp = 0;
	tmp = *left;
	*left = *right;
	*right = tmp;
}

3.向下調整演算法AdjustDown函式

現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，


上圖可知，先取出左右孩子小的節點，再和父節點比較，若比父節點小則交換兩個節點，在把原來的孩子節點當做父節點一直往下遍歷，
代碼如下：

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child<n)//(n > 0)
	{
		if (child + 1 < n&&a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

4.向上調整演算法AdjustUp函式

從倒數第一個非葉子節點從后往前，依次作為子樹向下調整，
代碼如下：

void AdjustUp(HPDataType* a,  int child)
{
	int parent = (child - 1) / 2;
	while ( child>0 ) //孩子大于0,則繼續回圈，否則終止回圈
	{
		if (a[child]>a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else  //已成為堆
		{
			break;
		}
	}
}

5.初始化堆HeapInit函式

因為堆物理結構是一個陣列，所以要考慮插入資料是否要動態增容，所以先判斷size和capacity的大小來決定是否要增容，然后建堆，建堆是建大堆，因為建小堆會打亂堆得結構，重新向下調整的話時間復雜度會增加，

代碼如下：

void HeapInit(struct Heap* hp, HPDataType* a, int n)     //初始化堆
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (hp->a == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	memcpy(hp->a, a, sizeof(HPDataType)*n);
	hp->size = n;
	hp->capacity=n;
	//建大堆
	int i = 0;
	for (i = (hp->size  - 2) / 2; i >= 0; i--)
	{
		AdjustDown(hp->a, hp->size, i);
	}
}

6.銷毀堆HeapDestory函式

直接釋放掉malloc開辟的空間，
代碼如下：

void HeapDestory(struct Heap* hp)                        //銷毀堆
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

7.堆的插入HeapPush函式

先判斷是否要增容，如果不用則在堆得尾部插入就是size的下標，然后重新向上調整即可，
代碼如下：

void HeapPush(struct Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)   //先判斷容量是否充足
	{
		//用realloc在已有空間在開辟一塊空間
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType)* hp->capacity*2);
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = hp->capacity * 2;
	}
	hp->a[hp->size ] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

8.堆的洗掉HeapPop函式

采用堆頂資料和堆底資料交換，然后洗掉堆底資料，在重新向下調整，
代碼如下：

void HeapPop(struct Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--; //洗掉掉堆底資料
	AdjustDown(hp->a, hp->size, 0);
}

9.取堆頂資料 HeapTop函式

因為物理結構是一個陣列，所以取下標為0的數就是堆頂資料，
代碼如下：

HPDataType HeapTop(struct Heap* hp)
{
	assert(hp);
	assert(hp->size != 0);
	return hp->a[0];
}

10.取堆資料個數 HeapSize函式

直接輸出size的大小，
代碼如下：

HPDataType HeapSize(struct Heap* hp)
{
	assert(hp);
	return hp->size;
}

11.堆判空 HeapEmpty函式

直接判斷堆資料size的大小是否為0，
代碼如下：

bool HeapEmpty(struct Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

12.列印堆HeapPrint函式

直接遍歷把堆中size個數的資料輸出來，
代碼如下：

void HeapPrint(struct Heap* hp)                          //列印堆
{
	assert(hp);
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

總結

以上就是今天要講的內容，本文僅僅簡單介紹了堆的使用，對于堆是一個完全二叉樹，而堆提供了大量能使我們快速便捷地處理資料的函式和方法，堆作為非線性表的一種，結構相對復雜，但是代碼實作相對容易，所以我們要好好掌握堆結構，另外，如果有需要原始碼的私信我即可，還有，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，