??紙上得來(lái)終覺(jué)淺， 絕知此事要躬行。
??主頁(yè)：June-Frost
??專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)

??該文章分別探討了向上建堆和向下建堆的復(fù)雜度和一些堆的經(jīng)典應(yīng)用 - 堆排列與topk問(wèn)題。

??該文章內(nèi)的思想需要用到實(shí)現(xiàn)堆結(jié)構(gòu)的一些思想（如向上調(diào)整和向下調(diào)整等），可以在另一篇文章《堆的順序?qū)崿F(xiàn)》中再次了解一下，其中一些接口有具體的實(shí)現(xiàn)??。

?? 建堆

?建堆的常見(jiàn)方式有兩種：向上建堆和向下建堆。

?? 向下建堆

?這些交換其實(shí)就是向下調(diào)整的過(guò)程，所以向下建堆只要通過(guò)不斷的向下調(diào)整就可以實(shí)現(xiàn)。

    int arr[] = { 10,20,25,35,60,36,15 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);//向下調(diào)整
	}

??時(shí)間復(fù)雜度

?將每層數(shù)據(jù)個(gè)數(shù) * 向下移動(dòng)的層數(shù)求和，得到 T(h) = 2^(h-2)*1 + 2^(h-3)*2+…+2¹ *(h-2) + 2⁰ *(h-1) 。通過(guò)錯(cuò)位相減，可以得到T(h) = 2^h-1-h。因?yàn)槭菨M(mǎn)二叉樹(shù)，所以假設(shè)節(jié)點(diǎn)為N，則N = 2^h - 1 , h = log₂(N+1) ，將h換為N，可以得到向下調(diào)整建堆合計(jì)調(diào)整次數(shù) T(N) = N-log(N+1)，所以時(shí)間復(fù)雜度為： O(N) 。

?? 向上建堆

?同樣，這些交換的思想就是向上調(diào)整，通過(guò)不斷調(diào)整就可以建堆。

    int i = 0;
	for (i = 1; i < n; i++)
	{
		AdjustUp(arr, i);//向上調(diào)整
	}

??時(shí)間復(fù)雜度

將次數(shù)求和，T(h) = 2¹*1 +2²2+…+2^h-2 * (h-2) + 2^h-1 * (h-1)。將h與N換算，得到T(N) = -N+(N-1)(log(N+1)-1)+1 ，總的來(lái)說(shuō)，時(shí)間復(fù)雜度為 O(N * logN) 。

???一棵滿(mǎn)二叉樹(shù)的最后一層節(jié)點(diǎn)數(shù)大概占據(jù)總數(shù)的50%，向上建堆在最后一層非常吃虧，不僅節(jié)點(diǎn)多，調(diào)整次數(shù)也多，而向下建堆避開(kāi)了最后一層，時(shí)間復(fù)雜度也優(yōu)于向上建堆，所以向下建堆比向上建堆更優(yōu)。

?? 堆的經(jīng)典應(yīng)用

?堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，通過(guò)大堆和小堆所帶來(lái)的特性可以使得堆在許多應(yīng)用中成為非常有效的數(shù)據(jù)結(jié)構(gòu)。

?? 堆排序

?堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法，它利用了堆的性質(zhì)來(lái)實(shí)現(xiàn)高效的排序。對(duì)于一個(gè)數(shù)組，雖然可以通過(guò)堆結(jié)構(gòu)來(lái)幫助排序，但是實(shí)現(xiàn)一整個(gè)堆的數(shù)據(jù)結(jié)構(gòu)并不容易，并且在建堆時(shí)會(huì)有額外空間的浪費(fèi)。

例如：通過(guò)堆數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序

int main()
{
	int arr[] = { 10,20,25,35,60,36,5 };
	HP heap;
	HeapInit(&heap);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		HeapPush(&heap, arr[i]);
	}
	int i = 0;
	while (!HeapEmpty(&heap))
	{
		arr[i++] =  HeapTop(&heap);
		HeapPop(&heap);
	}
	HeapDestroy(&heap);
	return 0;
}

? 基于這樣的一些缺點(diǎn)，所以最好可以實(shí)現(xiàn)原地排序。對(duì)于任意一個(gè)數(shù)組是可以看作一個(gè)完全二叉樹(shù)，但是不一定是堆，那么第一個(gè)步驟就是建堆。

?類(lèi)比堆的插入，可以將第一個(gè)數(shù)組元素看作堆，從第二個(gè)元素開(kāi)始進(jìn)行向上調(diào)整(前提 - 左右子樹(shù)依舊是堆），這樣就可以建堆。

void HeapSort(int* arr, int n)
{
	//第一步:建堆
	int i = 0;
	for (i = 1; i < n; i++)
	{
		AdjustUp(arr, i);
	}
}

?注意：

1. 升序：建大堆。
2. 降序：建小堆。

??分析：如果升序建造小堆

這樣的操作代價(jià)太大了,為 N*(N*logN)，甚至不如直接遍歷，喪失了堆的價(jià)值。

?當(dāng)我們想排升序，建造好大堆后，就可以利用堆刪除思想來(lái)進(jìn)行排序。

按照這個(gè)邏輯不斷交換和調(diào)整就可以完成排序，時(shí)間代價(jià)為 N*logN 。

void HeapSort(int* arr, int n)
{
	//第一步:建堆
	int i = 0;
	for (i = 1; i < n; i++)
	{
		AdjustUp(arr, i);//向上調(diào)整
	}
	//第二部：排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);//交換
		AdjustDown(arr, end, arr[0]);//向下調(diào)整
		end--;
	}
}

??TOPK問(wèn)題

?TOPK問(wèn)題是指從大量數(shù)據(jù)中獲取最大（或最小）的K個(gè)數(shù)據(jù)，例如：有大量的數(shù)據(jù)，這些數(shù)據(jù)在內(nèi)存中存儲(chǔ)不下，只能以文件形式存儲(chǔ)，現(xiàn)需要找出最大的前k個(gè)數(shù)。

方式：
1.讀取文件前k個(gè)數(shù)據(jù)，在內(nèi)存數(shù)組中建立一個(gè)小堆。
2.依次讀取剩下的數(shù)據(jù)，如果大于堆頂元素就進(jìn)行替換，并向下調(diào)整。

當(dāng)文件的數(shù)據(jù)全部讀取完成后，堆里的數(shù)據(jù)就是最大的前k個(gè)數(shù)。

??這里以10000個(gè)數(shù)據(jù)為例：

void PrintTok(const char* filename,int k)
{
	//用前k個(gè)數(shù)據(jù)建造一個(gè)小堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int i = 0;
	for (i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	//向下調(diào)整建堆
	for (i = (k - 2)/2 ; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}
	//遍歷剩下的數(shù)據(jù),大的數(shù)替代堆頂元素，然后向下調(diào)整
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
	    //如果大于堆頂元素就替換
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
	for (i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
	fclose(fout);
	free(minheap);
}
//造數(shù)據(jù)
void CreateNDate()
{
	int n = 10000;
	srand((unsigned int)time(NULL));
	const char* file = "Data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}
	for (int i = 0; i < n; i++)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

int main()
{
	//CreateNDate();//造數(shù)據(jù)
	PrintTok("Data.txt", 10);
	return 0;
}

?? 結(jié)語(yǔ)

?文章到這里就結(jié)束了，如果對(duì)你有幫助，你的點(diǎn)贊將會(huì)是我的最大動(dòng)力，如果大家有什么問(wèn)題或者不同的見(jiàn)解，歡迎大家的留言~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-714748.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】深度剖析最優(yōu)建堆及堆的經(jīng)典應(yīng)用 - 堆排列與topk問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！