国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

2年前作者：小沈熬夜禿頭中????分類：Toy博客閱讀(23)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

前言

??個(gè)人主頁：@小沈熬夜禿頭中????
??小編介紹：歡迎來到我的亂七八糟小星球??
??專欄：數(shù)據(jù)結(jié)構(gòu)
??本章內(nèi)容：堆排序+TOP-K問題
送給各位??：日落跌入昭昭星野 人間忽晚 山河以秋
記得 評論?? +點(diǎn)贊?? +收藏?? +關(guān)注??哦~

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

??一、建堆的兩種方式：

??1.1 向上調(diào)整建堆(堆排序)：

??1.1.1 完整代碼：

//Heap.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void AdjustDown(int* a, int n, int parent);
//因?yàn)橐赥est.c中調(diào)用這個(gè)函數(shù)而Test.c中包含#include"Heap.h"所以要在這里包含一下
void AdjustUp(HPDataType* a, int child);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

//Heap.c
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

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

//Test.c
void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 1;i<n; i++)
	{
	//堆向上調(diào)整算法
		AdjustUp(a, i);//當(dāng)i=0時(shí)，也就是孩子下標(biāo)是0此時(shí)一個(gè)數(shù)據(jù)可以看作一個(gè)堆所以從1開始向上調(diào)整
	}
	int end = n - 1;
	while (end > 0)
	{
		//小堆為例通過建堆第一個(gè)肯定是最小數(shù)
		Swap(&a[0], &a[end]);
		//調(diào)整選出次小數(shù)
		AdjustDown(a, end, 0);//這里的end是n-1是最后一個(gè)數(shù)據(jù)的下標(biāo)也是除了最后一個(gè)數(shù)據(jù)外前面數(shù)據(jù)的個(gè)數(shù)，所以可以傳end過去
		end--;
	}
}

int main()
{
	//HPTest();
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

??1.1.2 流程圖(以小堆為例)：升序：建大堆

最后得到的就是一個(gè)升序【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

??1.1.3 流程圖(以小堆為例)：降序：建小堆

最后得到的就是一個(gè)降序【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

??1.2 向下調(diào)整建堆(堆排序)：

??1.2.1 完整代碼：

//Heap.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void AdjustDown(int* a, int n, int parent);
void AdjustUp(HPDataType* a, int child);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
//Heap.c
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//Test.c
#include"Heap.h"
//直接建堆來調(diào)整---向下調(diào)整建堆
void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	//HPTest();
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

??1.2.2 流程圖：

【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

??二、兩種建堆方式時(shí)間復(fù)雜度比較：

通過對兩種建堆方式的比較更建議使用向下調(diào)整建堆但是向上調(diào)整建堆更容易理解看個(gè)人情況

??2.1 向上調(diào)整建堆：

【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

??2.2 向下調(diào)整建堆：

【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

??三、堆排序的時(shí)間復(fù)雜度：O(N*logN)

【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

??四、呼應(yīng)一下上章節(jié)的部分：利用堆使數(shù)據(jù)有序(不建議)

利用創(chuàng)建的堆數(shù)組排序:我們可以采用下面這種方法 — 先建堆(NlogN)太麻煩，然后來回拷貝數(shù)據(jù)(空間復(fù)雜度高)—具體代碼可以看【數(shù)據(jù)結(jié)構(gòu)】— 博主拍了拍你并向你扔了一“堆”二叉樹(堆的概念+結(jié)構(gòu)+代碼實(shí)現(xiàn))其中只有Test.c文件中做了以下修改其余沒變

void HeapSort(int* a,int n)
{
		HP hp;
		HeapInit(&hp);
		//建堆N*logN
		for (int i = 0;i<n; i++)
		{
			HeapPush(&hp, a[i]);
		}
		//N*logN
		int i = 0;
		while (!HeapEmpty(&hp))
		{
			int top = HeapTop(&hp);
			a[i++] = top;
			HeapPop(&hp);
		}
		for (int i = 0; i < n; i++)
		{
			printf("%d ", a[i]);
		}
		HeapDestroy(&hp);
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

??五、TOP-K問題：

??5.1 TOP-K問題思路：

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

對于Top-K問題，能想到的最簡單直接的方式就是排序
【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。
最佳的方式就是用堆來解決，基本思路如下：
【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)

??5.2 TOP-K問題代碼：

在1000個(gè)數(shù)中找到前5個(gè)最大的數(shù)

除了Test.c作了以下改變Heap.h和Heap.c依據(jù)上面

//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
#include<time.h>
void CreateNDate()
{
	// 造數(shù)據(jù)
	int n = 1000;
	srand(time(0));//產(chǎn)生隨機(jī)數(shù)
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");//以寫的形式打開文件
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);//寫
	}

	fclose(fin);
}

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");//以讀的方式
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	//malloc空間
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	//讀取前K個(gè)數(shù)據(jù)
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}
	//建堆(建小堆)
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k,i );
	}
	//比較覆蓋
	int val = 0;
	while (!feof(fout))//文件讀取結(jié)束就跳出循環(huán)
	{
		fscanf(fout, "%d", &val);//從k+1數(shù)據(jù)開始讀取和堆頂數(shù)據(jù)比較
		if (val > kminheap[0])
		{
			kminheap[0] = val;//覆蓋
			AdjustDown(kminheap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ",kminheap[i]);
	}
	printf("\n");
}

int main()
{
	CreateNDate();
	PrintTopK(5);

	return 0;
}

??六、文件操作：

可以看 C語言 — 文件操作(萬字詳解)

??總結(jié)

【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)
??Ending,今天的 堆排序+TOP-K問題 的內(nèi)容就到此結(jié)束啦~，如果后續(xù)想了解更多，就請關(guān)注我吧，一鍵三連哦 ~文章來源地址http://www.zghlxwxcb.cn/news/detail-460529.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】---堆排序+TOP-K問題(了解游戲排行底層原理)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包