目錄

堆的概念及結構

堆的邏輯結構與存盤結構

堆的實作

堆的插入

堆的創建

堆的洗掉

獲取堆頂的資料

堆的資料個數

堆的判空

堆的銷毀

實作堆的全部代碼

測驗用例

堆的概念及結構

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

堆的性質：

堆中某個節點的值總是不大于或不小于其父節點的值；

堆總是一棵完全二叉樹，

堆的邏輯結構與存盤結構

由于我們是把一個集合中的元素按二叉樹的順序存盤方式，存盤在一個一維陣列中，故堆的存盤結構是一個一維陣列，但我們是以二叉樹的順序存盤方式方式進行存盤，所以我們可以把這個一維陣列想象成一顆二叉樹，故堆的邏輯結構是一顆二叉樹，

堆的實作

先創建堆的結構體：

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

再給定一個陣列 arr，以建立小堆為例，

int a[] = { 27,15,19,18,28,34,65,49,25,37 };

注：這里創建堆的演算法是將陣列中的元素插入到堆中，然后再用向上調整演算法來建堆，故先說明堆的插入，關于直接將陣列改成堆，會在后面文章中給出，

堆的插入

先將元素插到堆的末尾，也就是在陣列的后面插入元素，然后再用向上調整演算法，將插入的元素調整至合適的位置，直到滿足堆，

向上調整演算法：

插入的元素不會影響從該元素到根上的其它元素，故只需要依次將插入的元素與其“父親”相比即可，若小于則交換，然后向上迭代，否則該元素已經到達滿足小堆的合適位置，

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustUp(int* 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 = (child - 1) / 2;
		}
		else
			break;
	}
}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

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

堆的創建

首先將堆初始化

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

此時堆為空，回圈呼叫堆的插入演算法即可

void HeapCreate(HP* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

	HeapInit(hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

堆的洗掉

堆的洗掉是洗掉堆頂的元素，首先將堆頂的元素與最后一個元素交換，然后洗掉最后一個元素，再使用向下調整演算法，將交換上來的元素調整至合適的位置，直到滿足堆，

向下調整演算法：

由于是建小堆，將該元素與它最小的一個“孩子”相比，若”孩子“更小，則將其交換，然后向下迭代，否則該元素已經到達滿足小堆的合適位置，

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
                                    //若建大堆這里的 < 改成 >
		if (child + 1 < n && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])//若建大堆這里的 < 改成 >
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* 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(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

堆的資料個數

堆結構體中的 size 保存了現有元素個數，直接將其回傳，

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

堆的判空

判斷堆中的 size 是否為 0 即可，

bool HeapEmpty(HP* hp)
{
	return hp->size == 0;
}

堆的銷毀

先將陣列釋放，再將堆的大小和容量置零，

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = hp->capacity = 0;
}

實作堆的全部代碼

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

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

void HeapCreate(HP* hp, HPDataType* a, int n);
void HeapDestroy(HP* hp);

void HeapPush(HP* hp, HPDataType x);
void AdjustUp(int* a, int child);
void HeapPop(HP* hp);
void AdjustDown(int* a, int n, int parent);

int HeapSize(HP* hp);
HPDataType HeapTop(HP* hp);
bool HeapEmpty(HP* hp);

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void HeapCreate(HP* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);
	HeapInit(hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = hp->capacity = 0;
}

void AdjustUp(int* 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 = (child - 1) / 2;
		}
		else
			break;
	}
}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

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

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

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

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

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

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

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

	return hp->a[0];
}

bool HeapEmpty(HP* hp)
{
	return hp->size == 0;
}

測驗用例

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

void TestHeap()
{
    int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP hp;
	HeapCreate(&hp, a, sizeof(a)/sizeof(a[0]));
    HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapDestroy(&hp);
}

int main()
{
	TestHeap();
	return 0;
}