堆的概念及結構

如果有一個關鍵碼的集合K = {k₀ ，k₁ ，k₂ ，…，k_n-1 }，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數組中，并滿足：k_i <=k_2*i+1 且 <=k_2*i+2 (k_i >=k_2*i+1 且 >=k_2*i+2 ) i = 0，1，2…，則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

堆的性質：
1.堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
2.堆總是一棵完全二叉樹。

根據數組下標我們可以得到父子結點下標之間的關系

堆的實現(xiàn)

堆其實就是一根完全二叉樹，我們可以采用數組的方式實現(xiàn)

初始化

//初始化
void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

銷毀

//銷毀
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

返回堆頂元素

//返回堆頂元素
HPDatatype HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpt(php));

	return php->a[0];
}

判空

//判空
bool HeapEmpt(Heap* php)
{
	assert(php);
	return php->size == 0;
}

有效數據個數

//數據個數
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}

堆的插入（向上調整算法）

插入一個數據，也要保持大堆或（小堆）

void Swap(HPDatatype* x, HPDatatype* y)
{
	HPDatatype tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上調整
void AdjustUp(HPDatatype* a, int child)
{
	int parent = (child - 1) / 2;
	//這里用孩子下標作為循環(huán)結束條件
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

//插入，仍保持堆的形態(tài)
void HeapPush(Heap* php, HPDatatype x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDatatype* tmp = (HPDatatype*)realloc(php->a, newcapacity * sizeof(HPDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;

	//向上調整
	AdjustUp(php->a, php->size - 1);
}

刪除堆頂元素，仍然保持堆的形態(tài)（向下調整算法）

刪除堆頂元素，是為了得到次大次少的元素。
既然用數組實現(xiàn)的堆，那刪除元素可以直接像順序表那樣把后邊元素向前移，覆蓋前面元素嗎？

顯然是不可以的，這個就稱不上堆了。
所以使用下面這種方法。

//向下調整
void AdjustDown(HPDatatype* a, int n, int parent)
{
	int minchild = parent * 2 + 1;
	while (minchild < n)
	{
		if (minchild + 1 < n && a[minchild+1] < a[minchild])
		{
			minchild++;
		}

		if (a[minchild] < a[parent])
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}
}

//刪除堆頂元素，仍然保持堆的形態(tài)
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpt(php));

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

	//向下調整
	AdjustDown(php->a, php->size, 0);
}

注意向下調整算法如果使用if和else來判斷該父節(jié)的孩子結點誰大誰小這樣會顯得代碼冗余，所以我們假設最小的是左孩子，然后左孩子和右孩子比較一下。看看那個是最小的，這樣我們的代碼會簡單很多。值得我們借鑒。

其實大家發(fā)現(xiàn)沒有，我們的建堆和堆排序已經完成了，

但是如果讓我們排序一組數據，難道我們要把寫一個堆然后在排序嗎？

首先把數組的數據拷貝到堆里，然后進行建堆排序，結果我們只是讓堆里面的數據變得有序了，數組里面的數據還是無序的，還得把堆里面數據拷貝回數組里，空間復雜度O(N);這樣實在太麻煩了。所以我們考慮一下直接對數組進行建堆排序。

堆的創(chuàng)建

我們這里建的都是小堆。如果建大堆的話，改一下符號就可以了。

向上調整法建堆

void HeapSort(int* a, int n)
{
	//向上調整法建堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
}

我們假設第一個元素就是一個堆，所以從下標為1的元素開始調整。

向下調整建堆

void HeapSort(int* a, int n)
{
	//向下調整法建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
}

最后一個結點下標n-1，（n-1-1）/ 2是最后一個非葉子結點下標。

兩種建堆方法時間復雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復雜度本來看的
就是近似值，多幾個節(jié)點不影響最終結果)：

向下調整法建堆時間復雜度分析

向上調整法建堆時間復雜度分析

因此建堆，我們應該選擇向下調整建堆法

堆排序

堆排序即利用堆的思想來進行排序，總共分為兩個步驟：

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

2. 利用堆刪除思想來進行排序
   建堆和堆刪除中都用到了向下調整，因此掌握了向下調整，就可以完成堆排序。

排序算法思想：每次交換第一個和最后一個元素，然后把最后一個元素不再看成堆里的元素，再進行向下調整（選擇次大次小的元素位于堆頂）。依次下次直到所有元素排序完畢。

void HeapSort(int* a, int n)
{
	//向上調整法建堆O(NlogN)
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}


	//向下調整法建堆O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	//堆排序O(NlogN)
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}

TOP-k問題

TOP-K問題：即求數據結合中前K個最大的元素或者最小的元素，一般情況下數據量都比較大。
比如：專業(yè)前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。

假設我們要求給出數據前K個最大的元素。我們用堆有三種思路解決這個問題

1.堆排序
2.建大堆，把N個元素建成大堆，堆頂就是最大的元素，取堆頂元素，然后再Pop堆頂元素，總共Pop k次。
3.建小堆，把前k的元素建小堆，后N-k個元素于堆頂元素比較，比堆頂元素大就讓該元素占據堆頂位置，然后再調整堆。

分析一下每種方法時間復雜度把。
堆排序O(Nlog₂N);

建大堆，建堆O(N),調整堆O(log₂N),總共調整K次，時間復雜度O(N+log₂N*K)，空間復雜度O(N)

建小堆，建堆O(K),調整堆O(log₂K),假設最壞調整N-K次，時間復雜度O(K+log₂K*(N-K)),約等于O(N),空間復雜度O(K)

還可以從下面這個角度再分析。
如果數據很大有100w個，而我們只取很小的K呢。代入時間時間復雜度看一看。

所以解決TOP-K問題最佳方式：

1. 用數據集合中前K個元素來建堆
   前k個最大的元素，則建小堆
   前k個最小的元素，則建大堆
2. 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素
   將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。

下面是生成隨機數放在文件里，再從文件讀取K個數據建成小堆，再把N-K個與堆頂元素進行比較。。。。關于想了解文件的請點擊這里文件然后結合看下面代碼。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void GenerateFile(const char* filename, int N)
{
	//把數據寫入文件里
	FILE* fin = fopen(filename, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}

	srand((unsigned int)time(NULL));

	//寫
	for (int i = 0; i < N; i++)
	{
		fprintf(fin, "%d ", rand());
	}


	fclose(fin);
}

void PrintTopk(const char* filename, int k)
{
	//把文件中數據讀到內存
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* minHeap = (int*)malloc(k * sizeof(int));
	if (minHeap == NULL)
	{
		perror("malloc fail");
		return;
	}

	//讀k個數據
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//將k個數據建成小堆
	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, k, i);
	}

	int val = 0;
	//繼續(xù)讀取N-K個元素
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			//調整堆
			AdjustDown(minHeap, k, 0);
		}
	}

	//打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}

	fclose(fout);

}
int main()
{
	const char* filename = "Data.txt";
	int k = 10;
	int N = 10000;
	GenerateFile(filename, N);
	PrintTopk(filename, k);

	return 0;
}

為了驗證這個代碼是否正確，我們可以把這段代碼

	//寫
	for (int i = 0; i < N; i++)
	{
		fprintf(fin, "%d ", rand());
	}

改成

	//寫
	for (int i = 0; i < N; i++)
	{
		fprintf(fin, "%d ", rand()%10000);
	}

這樣就得到隨機數為10000里的數字，再在文件里添加10001-10010，千萬注意不要再生成文件了，不然你的數據就會被覆蓋。然后打印，是我們想要的結果。

自此關于堆的實現(xiàn)，建堆，堆排序以及TOP-K問題再一篇文章里都解決了，歡迎有問題的小伙伴們再評論區(qū)提問，點贊，收藏。一鍵三連哦！萬分感謝！文章來源地址http://www.zghlxwxcb.cn/news/detail-440513.html

到了這里，關于堆的實現(xiàn)，畫圖和代碼分析建堆，堆排序，時間復雜度以及TOP-K問題的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！