重要的概念

要講到堆，先要說(shuō)兩個(gè)關(guān)于二叉樹(shù)的概念

1. 滿二叉樹(shù)：一個(gè)二叉樹(shù)如果每一層的節(jié)點(diǎn)數(shù)都是最大值，那么這個(gè)二叉樹(shù)就是滿二叉樹(shù)
   

2. 完全二叉樹(shù)：完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是滿二叉樹(shù)的變形，對(duì)于深度為k的樹(shù)有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的節(jié)點(diǎn)
   
   上面所展示的就是滿二叉樹(shù)和完全二叉樹(shù)

樹(shù)的存儲(chǔ)方式

順序存儲(chǔ)

任何一個(gè)數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中都要以一定的方式存儲(chǔ)起來(lái)，那么具體如何存儲(chǔ)起來(lái)？有下面的規(guī)則

首先是順序存儲(chǔ)，也就是用順序表的形式存儲(chǔ)，存儲(chǔ)形式如下：

但很明顯，這樣的存儲(chǔ)對(duì)于非完全二叉樹(shù)來(lái)說(shuō)會(huì)造成十分嚴(yán)重的內(nèi)存浪費(fèi)

鏈?zhǔn)酱鎯?chǔ)

鏈?zhǔn)酱鎯?chǔ)相比起順序存儲(chǔ)各有優(yōu)勢(shì)，鏈?zhǔn)酱鎯?chǔ)的規(guī)則如下：

定義一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體中包含這三個(gè)成員，這三個(gè)成員就可以包含一個(gè)樹(shù)的所有信息

下面重點(diǎn)介紹的是二叉樹(shù)的順序結(jié)構(gòu)是如何實(shí)現(xiàn)的

堆的概念

首先要明確，這里的堆和malloc的堆并不是一個(gè)意思，前者的意思是一種數(shù)據(jù)結(jié)構(gòu)，而后者是操作系統(tǒng)的一部分區(qū)域

堆是一種完全二叉樹(shù)，它滿足下面的性質(zhì)

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

那為什么是不大于或不小于？因?yàn)槎岩彩怯袆澐值?，堆分為大堆和小?/p>

在介紹大堆和小堆之前，先說(shuō)明堆的順序存儲(chǔ)是如何存儲(chǔ)的，以下面這個(gè)圖為例

上圖是一個(gè)完全二叉樹(shù)，其中二叉樹(shù)的父親節(jié)點(diǎn)總是小于孩子節(jié)點(diǎn)，那么這就是小堆，而在內(nèi)存中的存儲(chǔ)形式如下圖所示，存儲(chǔ)的時(shí)候確實(shí)是按照數(shù)組存儲(chǔ)，順序遵循由上到下由左到右的順序進(jìn)行存儲(chǔ)

大堆和上圖基本一致，之時(shí)父親節(jié)點(diǎn)總是大于孩子節(jié)點(diǎn)

堆的實(shí)現(xiàn)

那么作為一種數(shù)據(jù)結(jié)構(gòu)，它會(huì)有它自己的用途，下面分析堆是如何實(shí)現(xiàn)的

從上述的存儲(chǔ)結(jié)構(gòu)可以看出，實(shí)際上每一個(gè)數(shù)組都可以把它看成是一個(gè)二叉樹(shù)，由于堆的特殊性，首要問(wèn)題就是如何把一個(gè)數(shù)組中的數(shù)字排序滿足堆的要求

向上調(diào)整算法

這個(gè)算法主要是用來(lái)進(jìn)行堆中元素的插入，當(dāng)插入一個(gè)元素，由于大堆/小堆，這個(gè)插入的元素可能不符合堆的要求，這時(shí)候就需要用到向上調(diào)整算法

該算法的應(yīng)用場(chǎng)景就是當(dāng)一個(gè)元素要插入一個(gè)堆時(shí)，可以用這個(gè)算法進(jìn)行插入，使得后續(xù)的二叉樹(shù)依舊是堆，前提是插入前的二叉樹(shù)必須滿足堆的要求

該算法的流程是這樣的

首先，原本有一個(gè)堆，有一個(gè)新元素12要插入這個(gè)堆中，它的位置應(yīng)該是作為15的孩子節(jié)點(diǎn)，但由于小堆的規(guī)則，12小于15，因此這里的12應(yīng)該和15交換一下位置，接著12再和它的上一代比較，發(fā)現(xiàn)12小于10，滿足小堆的規(guī)則，因此新堆就變成了右圖所示的模樣，至此就完成了堆的插入

這里不得不提的是，插入的元素要進(jìn)行向上調(diào)整算法的最終目標(biāo)是它的祖先，只要它和上一代之間不滿足規(guī)則，就一直交換，直到它成為了它所在的這一代的祖先為止

一些實(shí)現(xiàn)過(guò)程中的技巧

知道了孩子節(jié)點(diǎn)的序號(hào)如何求父節(jié)點(diǎn)？

由于計(jì)算機(jī)除號(hào)的取整性，父親節(jié)點(diǎn) == ( 孩子節(jié)點(diǎn)-1 ) / 2

實(shí)現(xiàn)搭建堆

根據(jù)上面的兩個(gè)步驟，我們就可以開(kāi)始搭建堆了

首先是把數(shù)組插入到堆中

int main()
{
	HP hp;
	HeapInit(&hp);
	int arr[] = { 9,8,6,5,43,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < sz; i++)
	{
		HeapPush(&hp, arr[i]);
	}

	return 0;
}

這里假設(shè)直接插入，沒(méi)有進(jìn)行任何算法調(diào)位，那么結(jié)果應(yīng)該是這樣的

如果用向上調(diào)整算法進(jìn)行調(diào)整，后面的結(jié)果是這樣的

void Swap(HPDataType* child, HPDataType* parent)
{
	HPDataType tmp;
	tmp = *child;
	*child = *parent;
	*parent = tmp;
}

void AdjustUp(HP* php, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (php->a[child] < php->a[parent])
		{
			Swap(&php->a[child], &php->a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		php->a = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);
		if (php->a == NULL)
		{
			perror("malloc fail");
			return;
		}
	}

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

	AdjustUp(php, php->size - 1);
}

從中可以看出，這樣的算法是可以進(jìn)行堆正確排序的，這樣，堆就搭建起來(lái)了

下面我們進(jìn)行堆相關(guān)的其他操作

實(shí)現(xiàn)出堆的操作

有數(shù)據(jù)入堆就少不了出堆，那么數(shù)據(jù)是如何出堆的？

首先要明確是誰(shuí)出堆，初學(xué)可能會(huì)認(rèn)為是堆的最后一個(gè)元素，事實(shí)上，這樣的操作是沒(méi)有意義的，因此這里出堆，出的是堆頂?shù)脑兀敲磫?wèn)題就來(lái)了，如何實(shí)現(xiàn)出堆的功能？

如果你不加思考去想，這個(gè)功能很簡(jiǎn)單，直接把數(shù)組后面的內(nèi)容覆蓋不就好了嗎？事實(shí)上，這樣的想法是錯(cuò)誤的，原因在于覆蓋后的堆還能維持原來(lái)的現(xiàn)狀嗎？原來(lái)的父子關(guān)系會(huì)變成兄弟關(guān)系，原來(lái)的兄弟關(guān)系也會(huì)因?yàn)樯倭艘粋€(gè)元素而發(fā)生改變，這整個(gè)過(guò)程會(huì)有很大變化，因此，這里引入了第二個(gè)算法，向下調(diào)整算法

這個(gè)算法設(shè)計(jì)也是很巧妙，假設(shè)我們現(xiàn)在搭建的是小堆，那么堆頂?shù)脑厥亲钚≡?，現(xiàn)在我們讓堆頂這個(gè)最小元素和整個(gè)堆的最后一個(gè)元素互換位置，那么此時(shí)堆頂元素變成另外一個(gè)元素，但是堆的其他部分依舊符合小堆的規(guī)則(交換的原來(lái)的最小值堆頂就不計(jì)入堆中了，已經(jīng)被pop掉了)，那么接著就可以采用向下調(diào)整算法，讓這個(gè)新的堆頂元素向下調(diào)整，這樣就能實(shí)現(xiàn)目標(biāo)

下面的圖可以很好的解釋這個(gè)原理

那么現(xiàn)在就要搞清楚什么是向下調(diào)整算法

向下調(diào)整算法

首先聲明這個(gè)算法的使用條件，該算法適用于除了堆頂外的其他部分都滿足小堆或大堆的條件時(shí)，可以使用，簡(jiǎn)單來(lái)說(shuō)就是pop堆頂?shù)臅r(shí)候可以使用

使用的原理也相當(dāng)簡(jiǎn)單，假設(shè)我們這里是小堆，那么堆頂元素被彈出，此時(shí)堆中第二小的元素一定是這個(gè)堆頂元素的兒子，那么我們就讓堆的最后一個(gè)葉子來(lái)充當(dāng)這個(gè)新的堆頂，這樣可以在保持堆整體的構(gòu)造不變的前提下還能把堆頂元素彈出，緊接著就讓這個(gè)堆頂元素和下面的兒子進(jìn)行比較，誰(shuí)小誰(shuí)就是新的堆頂，進(jìn)行交換后第二小的元素就產(chǎn)生了，當(dāng)然，如果樹(shù)的高度很高，那么交換后可能需要繼續(xù)交換，知道這個(gè)葉子回到最后一層，這個(gè)過(guò)程也是可以借助循環(huán)實(shí)現(xiàn)的，借助這個(gè)向下調(diào)整算法就可以把堆頂元素彈出的同時(shí)還能變成一個(gè)新堆，不斷的找出最小的值或最大的值

那么下面我們來(lái)實(shí)現(xiàn)這個(gè)算法

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

void HeapPop(HP* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

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

堆排序

下面說(shuō)明堆的另外一個(gè)作用，可以用來(lái)堆排序

首先說(shuō)明堆排序的原理：假設(shè)現(xiàn)在這里有10個(gè)數(shù)字，現(xiàn)在把這10個(gè)數(shù)字建成小堆，那么堆頂?shù)脑鼐褪沁@10個(gè)數(shù)字的最小值，再讓該數(shù)字和最后一個(gè)元素呼喚位置，這樣最小值就到了最后一個(gè)位置，再進(jìn)行向下調(diào)整算法可以調(diào)整出第二小的元素，按照上方的流程重新來(lái)一次，就能弄出新的數(shù)字，這樣下去就可以實(shí)現(xiàn)降序排列的功能

具體操作流程如下

void HeapSort(HPDataType* a, int size)
{
	assert(a);

	//建堆
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, size, i);
	}
	
	//排序
	int end = size - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

這樣的排序也是有效的

那么堆排序好在哪里？從時(shí)間復(fù)雜度來(lái)看，堆排序的時(shí)間復(fù)雜度只有O(NlogN)，整體來(lái)看效率還是可以的

TopK

堆真正強(qiáng)大的功能其實(shí)是強(qiáng)大在從很大一個(gè)量級(jí)的數(shù)字中要找出其中最大或最小的10個(gè)，假設(shè)這個(gè)數(shù)字是一億甚至十億，那么如果我們還采用的是正常的排序來(lái)看，那么整個(gè)過(guò)程就會(huì)相當(dāng)麻煩，把這些數(shù)字全部排序再找最大或最小的幾個(gè)，這個(gè)過(guò)程消耗的時(shí)間和空間復(fù)雜度是不可計(jì)算的，甚至計(jì)算機(jī)沒(méi)有足夠的內(nèi)存供你建立如此龐大的空間

因此堆可以很好的解決這個(gè)問(wèn)題，堆的功能主要體現(xiàn)在它可以篩選出你要的數(shù)據(jù)，下面介紹topk的原理

假設(shè)我們現(xiàn)在有10000個(gè)數(shù)字，我們要從中找到最大的5個(gè)，那么如何用堆來(lái)進(jìn)行實(shí)現(xiàn)？
首先，我們把前五個(gè)數(shù)字建一個(gè)堆，假設(shè)我們要找的是最大的五個(gè)數(shù)，那么我們就建立小堆，然后讓后面的數(shù)字依次從堆頂看能不能進(jìn)入堆中，假設(shè)這個(gè)數(shù)字大于堆頂元素，那么就讓這個(gè)元素稱為堆頂元素，再進(jìn)行向下調(diào)整，接著讓下一個(gè)元素和堆頂比較…

按這樣的想法實(shí)施下來(lái)，就可以使得堆中的元素是所有數(shù)字里面最大的五個(gè)元素，這樣就能實(shí)現(xiàn)目標(biāo)

下面就來(lái)模擬實(shí)現(xiàn)這個(gè)過(guò)程

首先，我們要獲取到這10000個(gè)數(shù)據(jù)，下面展示獲取數(shù)據(jù)量的一種途徑

void CreateData()
{
	int n = 10000;
	srand(time(0));
	FILE* pf = fopen("test.txt", "w");
	if (pf == NULL)
	{
		perror("fopen fail");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = rand() % 10000;
		fprintf(pf, "%d\n", x);
	}
	fclose(pf);
}

獲取了信息下面開(kāi)始實(shí)現(xiàn)topk的功能文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-611952.html

void PrintTopK()
{
	Heap hp = { 0,0,0 };
	HeapCreate(&hp,hp.a,4);
	FILE* pf = fopen("test.txt", "r");
	if (pf == NULL)
	{
		perror("fopen fail");
		return;
	}
	int* kmaxheap = (int*)malloc(sizeof(int) * 5);
	if (kmaxheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	for (int i = 0; i < 5; i++)
	{
		fscanf(pf, "%d", &kmaxheap[i]);
		HeapPush(&hp, kmaxheap[i]);
	}
	int val = 0;
	while (!feof(pf))
	{
		fscanf(pf, "%d", &val);
		if (val > kmaxheap[0])
		{
			kmaxheap[0] = val;
			AdjustDown(kmaxheap, 5, 0);
		}
	}
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", kmaxheap[i]);
	}
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：手撕圖解堆的實(shí)現(xiàn)和TopK的應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！