堆排序和TopK問題（C語言實現(xiàn)）-創(chuàng)新互聯(lián)

文章目錄：

1.堆排序
- 1.1向上調(diào)整和向下調(diào)整建堆對比
- 1.2堆排序?qū)崿F(xiàn)
- - 1.2.1升序
  - 1.2.2降序
2.Top-K問題
- 2.1解決思路
- 2.2代碼實現(xiàn)

為安義等地區(qū)用戶提供了全套網(wǎng)頁設計制作服務，及安義網(wǎng)站建設行業(yè)解決方案。主營業(yè)務為成都做網(wǎng)站、成都網(wǎng)站設計、安義網(wǎng)站設計，以傳統(tǒng)方式定制建設網(wǎng)站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

前面的文章講了堆的結(jié)構(gòu)和基礎接口實現(xiàn)，不熟的友友們可以去看看堆（C語言實現(xiàn)），點擊跳轉(zhuǎn)

1.堆排序

堆排序即利用堆的思想來進行排序
升序：建大堆
降序：建小堆

1.1向上調(diào)整和向下調(diào)整建堆對比

上一篇文章我們講了建堆的接口，咱么用的是向下調(diào)整建堆，那為什么不用向上調(diào)整建堆呢？下面我們就來對比一下那種方法更優(yōu)

向上調(diào)整建堆時間復雜度圖解：

向下調(diào)整建堆時間復雜度圖解：

由圖解我們得到結(jié)論：
向上調(diào)整建堆的時間復雜度為：O(N*log₂(N))；向下調(diào)整建堆的時間復雜度為：O(N)

1.2堆排序?qū)崿F(xiàn) 1.2.1升序

升序，建大堆
首先交換堆的首尾數(shù)據(jù)，把大的數(shù)放在尾部，再從根節(jié)點開始向下調(diào)整size-1個數(shù)據(jù)（遞減：從size-1開始每放一個數(shù)據(jù)就 -1，也就是不對交換到尾部的元素進行調(diào)整）

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下調(diào)整（建大堆）
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;//假定左孩子
	while (child< n)
	{//大堆：保證child指向大的那個孩子
		if (a[child + 1] >a[child] && child + 1< n)
		{	child++;
		}
		//大堆：孩子大于父親就交換，并繼續(xù)向下比較調(diào)整，反之則調(diào)整結(jié)束
		if (a[child] >a[parent])
		{	Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{	break;
		}
	}
}

//堆排序
//升序：建大堆
void HeapSort(int* a, int n)
{//建堆算法
	//從最后一個元素的父節(jié)點開始依次向前可以遍歷到每顆子樹的父節(jié)點
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end >0)
	{//交換首尾數(shù)據(jù)
		Swap(&a[0], &a[end]);
		//從首元素開始向下調(diào)整
		AdjustDown(a, end, 0);
		--end;
	}
}

1.2.2降序

降序，建小堆
首先交換堆的首尾數(shù)據(jù)，把最小的數(shù)放在尾部，再從根節(jié)點開始向下調(diào)整size-1個數(shù)據(jù)（遞減：從size-1開始每放一個數(shù)據(jù)就 -1，也就是不對交換到尾部的元素進行調(diào)整）

//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下調(diào)整（建小堆）
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;//假定左孩子
	while (child< n)
	{//小堆：保證child指向小的那個孩子
		if (a[child + 1]< a[child] && child + 1< n)
		{	child++;
		}
		//小堆：孩子小于父親就交換，并繼續(xù)向下比較調(diào)整，反之則調(diào)整結(jié)束
		if (a[child]< a[parent])
		{	Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{	break;
		}
	}
}

//堆排序
//降序：建小堆
void HeapSort(int* a, int n)
{//建堆算法
	//從最后一個元素的父節(jié)點開始依次向前可以遍歷到每顆子樹的父節(jié)點
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end >0)
	{//交換首尾數(shù)據(jù)
		Swap(&a[0], &a[end]);
		//從首元素開始向下調(diào)整
		AdjustDown(a, end, 0);
		--end;
	}
}

2.Top-K問題

什么是Top-K問題？

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

2.1解決思路

對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。最佳的方式就是用堆來解決，基本思路如下：

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

2.2代碼實現(xiàn)

根據(jù)上面的思路，來舉兩個栗子

1.求有10000個數(shù)據(jù)的數(shù)組中大的10個數(shù)

//Top-K問題
void Topk()
{int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	//使數(shù)組中的數(shù)都在1000000以內(nèi)
	for (size_t i = 0; i< n; ++i)
	{a[i] = rand() % 1000000;
	}
	//手動設置10個大于1000000的數(shù)
	a[12] = 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;
	//將數(shù)組a中前k個數(shù)據(jù)讀到數(shù)組minHeap中
	int k = 10;
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{perror("malloc fail");
		return;
	}
	for (int i = 0; i< k; ++i)
	{a[i] = minHeap[i];
	}
	//建一個k個大小的小堆minHeap
	for (int h = (k - 1 - 1) / 2; h >= 0; --h)
	{AdjustDown(minHeap, k, h);
	}
	//遍歷數(shù)組中的剩余數(shù)與堆頂比較，大于則替換并向下調(diào)整
	for(int j = k;j< n; ++j)
	{if (a[j] >minHeap[0])
		{	minHeap[0] = a[j];
			AdjustDown(minHeap, k, 0);
		}
	}
	//打印小堆數(shù)據(jù)即為數(shù)組a中大的10個數(shù)
	for (int g = 0; g< k; ++g)
	{printf("%d ", minHeap[g]);
	}
	printf("\n");
}

2.從文件中讀取數(shù)據(jù)求大的前k的

//Top-K問題
void Topk()
{//寫數(shù)據(jù)到文件中
	int n, k;
	printf("請輸入在n個數(shù)中選取大的k個數(shù):>");
	scanf("%d%d", &n, &k);
	srand(time(0));
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{perror("fopen fail");
		return;
	}
	for (size_t i = 0; i< n; ++i)
	{int val = rand();
		fprintf(fin, "%d\n", val);
	}
	fclose(fin);

	//找topk
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{perror("fopen fail");
		return;
	}
	//開辟k個大小的數(shù)組
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{perror("malloc fail");
		return;
	}
	//將文件中的前k個數(shù)據(jù)讀到數(shù)組中
	for (int i = 0; i< k; ++i)
	{fscanf(fout, "%d", &minHeap[i]);
	}
	//建一個k個大小的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(minHeap, k, i);
	}
	int val = 0;
	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]);
	}
	printf("\n");

	fclose(fout);
}

運行結(jié)果：
TopK問題圖解（大的前k個數(shù)舉例）：

堆排序和TopK問題到這里就介紹結(jié)束了，期待大佬們的三連！你們的支持是我大的動力！
文章有寫的不足或是錯誤的地方，歡迎評論或私信指出，我會在第一時間改正。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當前標題：堆排序和TopK問題（C語言實現(xiàn)）-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://aaarwkj.com/article46/pghhg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、電子商務、網(wǎng)站設計、網(wǎng)站收錄、靜態(tài)網(wǎng)站、App設計

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

堆排序和TopK問題（C語言實現(xiàn)）-創(chuàng)新互聯(lián)