【資料結構】 堆的簡單理解和代碼實作

前言：本章將詳細介紹堆，并通過代碼創建堆、實作一些堆的基本操作，最后以TopK問題為文章結尾， By the way,咱們資料結構中的堆是一種資料結構，堆必然是完全二叉樹，而系統層的堆是作業系統中管理記憶體的一塊區域分段，注意區分開，

1.堆的概念、性質

什么是堆：

堆(Heap)是計算機科學中一類特殊的資料結構的統稱，堆通常是一個可以被看做一棵完全二叉樹的陣列物件，

堆的性質：

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

2.堆總是一棵完全二叉樹，

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，常見的堆有二叉堆、斐波那契堆等，堆是非線性資料結構，相當于一維陣列，有兩個直接后繼，

2.堆的代碼實作和基本操作

定義堆

typedef int HPDataType;

//定義大堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

堆的向上調整

從葉子節點插入一個元素后，想要繼續保持堆的結構不變，從下往上，對二叉樹進行調整，確保最后是小堆，

圖示程序如下：

1.未進行插入新元素的堆：

2.新元素0

3.新元素0跟此時的父親節點5比較，比5小，交換

4.然后0繼續和新的父親節點2比較，比2小，交換

5.然后0繼續和新的父親節點0進行比較，比1小，交換

6.此時的child已經達到while (child > 0)的結束條件了，退出回圈，新的小堆調整完畢，

void swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

//前提：原本的堆就是小堆
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	//這里可以思考下為什么while的條件不適用parent>=0，因為parent不可能小于0
	while (child > 0)
	{
		//只要插入的葉子節點比父親節點小就進行交換，并不斷進行回圈，直至達到結束條件
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的向下調整

比如當我們洗掉了堆頂第一個元素后，想要保持剩下的元素還是堆的結構時，可以考慮把最后一個葉子節點移動到堆頂，然后使用一次AdjustDown，

圖示程序如下：

1.往堆頂插入新元素5

2.元素5跟左右孩子中小的那個進行比較，若比他大，就交換

3.繼續與左右孩子中小的進行比較，若更大，就交換

4.繼續比較，發現并不會比孩子節點小，跳出回圈，新的小堆調整結束，

//堆從上到下進行調整(前提條件是：左右子樹都是小堆)
void AdjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		//選出左右孩子當中小的那個孩子
		if (a[child + 1] < a[child])
		{
			child++;
		}

		//從上到下，如果小的那個孩子比父親節點還小，那就交換
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			//child = parent;
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆的初始化

這里以建立小堆為例，我們需要保證小堆的結構，這里通過自下而上進行調整，

這里提一嘴為什么建堆程序中的for回圈內i初始值設定為（n-1-1）/2，首先陣列最后一個元素下標是n-1,又有child=2*parent+1,帶入后就是這個初始值，

void HeapInit(HP* php, int* a, int n)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}

	memcpy(php->a, a, sizeof(HPDataType) * n);

	//建堆，從下往上反復呼叫函式AdjustDown，建立小堆
	for (int i = (n - 1 - 1) / 2; i >= 0;--i)
	{
		AdjustDown(php->a, n, i);
	}

	php->size = n;
	php->capacity = n;
}

堆的銷毀

直接free掉a，然后把php->a置空，并把size和capacity置0

void HeadDestroy(HP* php)
{
	assert(php);

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

堆的插入操作

1.先判斷下空間是否滿了，若滿了，realloc開辟一塊新的空間，沒滿就不需要開辟，

2.然后把新插入的元素放在最后一個葉子節點處

3.接下來與其雙親結點進行比較,如果比雙親結點小,就交換其值,一直不斷重疊

4.最后如果該資料比雙親結點值大,就結束調整;如果當child等于0,就結束調整

void HeadPush(HP* php, HPDatatype x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity);
		if (php->a == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	php->size++;

	//從下往上進行調整，保持堆的結構不變
	AdjustUp(php->a, php->size - 1);
}

堆的洗掉操作

該函式的作用是洗掉堆頂元素,并且不能毀壞堆結構，如果是你，你會寫出怎樣的代碼來實作？

這里借助堆排序的思想,直接把堆頂第一個元素和堆底第一個元素交換，然后php->size減1，再呼叫一次自上而下的排序，因為size減1了，相當于除了原本堆頂第一個元素以外的元素進行調整，

void HeadPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	//這個地方太妙了 兄弟們！！！ 
	swap(&a[0], a[php->size - 1]);
	php->size--;

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

獲取堆頂的元素

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

	return php->a[0];
}

堆的判空

bool HeadEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

堆內元素數量

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

列印堆內元素

void HeapPrint(HP* php)
{
	assert(php);

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

3.TopK問題(即在N個數當中，選出最大/小的K個元素)

例：從（N）10億個整數當中挑選最大的（K）10個，怎么做？

首先思考下建立大堆還是小堆？

答：建小堆，因為如果建大堆，最大的數可能擋在頭的位置，其他9個次大的數就進不來，

接下來怎么建這個擁有10億個整數的堆呢？

思路一：建一個擁有10億個數的小堆，建堆的時間復雜度是O(N)，K個數選出來是O（KlogN），時間復雜度為O(N+KlogN)，這個復雜度太高了，能不能優化下？

思路二：建一個10個數的小堆，將10個數以外的數依次放入堆中，建堆的時間復雜度O(K)，找到K個數的時間復雜度為（NlogK），總時間復雜度就是O(K+N*logK)，

復現思路二的代碼：

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	for (int i = k; i < n; ++i)
	{
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}

	HeapPrint(&hp);

	HeapDestroy(&hp);
}

void TestTopk()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	//隨機賦值十個最大的數
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;

	PrintTopK(a, n, 10);
}

補充下將一個順序表整理成堆的時間復雜度推導：

4.原始碼鏈接

https://gitee.com/linkylo/c_code_2021/tree/master/c_code_2021_9_3(Lab%EF%BC%89

資料結構堆的代碼實作和相關的TopK問題的內容到此介紹結束了，感謝您的閱讀！！！如果內容對你有幫助的話，記得給我點個贊——做個手有余香的人，