【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

这篇具有很好参考价值的文章主要介绍了【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

👧个人主页:@小沈熬夜秃头中୧⍤⃝❅
😚小编介绍:欢迎来到我的乱七八糟小星球🌝
📋专栏:数据结构
🔑本章内容:堆排序+TOP-K问题
送给各位💌:日落跌入昭昭星野 人间忽晚 山河以秋
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~


提示:以下是本篇文章正文内容,下面案例可供参考

🌟一、建堆的两种方式:

🌏1.1 向上调整建堆(堆排序):

💫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);
//因为要在Test.c中调用这个函数而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++)
	{
	//堆向上调整算法
		AdjustUp(a, i);//当i=0时,也就是孩子下标是0此时一个数据可以看作一个堆所以从1开始向上调整
	}
	int end = n - 1;
	while (end > 0)
	{
		//小堆为例通过建堆第一个肯定是最小数
		Swap(&a[0], &a[end]);
		//调整选出次小数
		AdjustDown(a, end, 0);//这里的end是n-1是最后一个数据的下标也是除了最后一个数据外前面数据的个数,所以可以传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 流程图(以小堆为例):升序:建大堆

最后得到的就是一个升序【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

💫1.1.3 流程图(以小堆为例):降序:建小堆

最后得到的就是一个降序【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

🌏1.2 向下调整建堆(堆排序):

💫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"
//直接建堆来调整---向下调整建堆
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 流程图:

【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

🌟二、两种建堆方式时间复杂度比较:

通过对两种建堆方式的比较更建议使用向下调整建堆但是向上调整建堆更容易理解看个人情况

🌏2.1 向上调整建堆:

【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

🌏2.2 向下调整建堆:

【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

🌟三、堆排序的时间复杂度:O(N*logN)

【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

🌟四、呼应一下上章节的部分:利用堆使数据有序(不建议)

利用创建的堆数组排序:我们可以采用下面这种方法 — 先建堆(NlogN)太麻烦,然后来回拷贝数据(空间复杂度高)—具体代码可以看【数据结构】— 博主拍了拍你并向你扔了一“堆”二叉树(堆的概念+结构+代码实现)其中只有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问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序
【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
最佳的方式就是用堆来解决,基本思路如下:
【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

🌏5.2 TOP-K问题代码:

在1000个数中找到前5个最大的数

除了Test.c作了以下改变Heap.h和Heap.c依据上面

//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
#include<time.h>
void CreateNDate()
{
	// 造数据
	int n = 1000;
	srand(time(0));//产生随机数
	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个数据
	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))//文件读取结束就跳出循环
	{
		fscanf(fout, "%d", &val);//从k+1数据开始读取和堆顶数据比较
		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语言 — 文件操作(万字详解)


😽总结

【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)
😽Ending,今天的 堆排序+TOP-K问题 的内容就到此结束啦~,如果后续想了解更多,就请关注我吧,一键三连哦 ~文章来源地址https://www.toymoban.com/news/detail-460529.html

到了这里,关于【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-堆的实现及应用(堆排序和TOP-K问题)

    1.堆的知识点: 下面我们通过一张图片来更加深刻地理解堆 上面我们说过,堆的物理结构是一个数组,逻辑结构是一个完全二叉树,所以堆的实际结构类似于顺序表,只不过我们的处理方式类似于二叉树 那么我们就可以用顺序表那样的结构来表示堆了 于是我们可以写出这样的代码

    2024年02月07日
    浏览(52)
  • 【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​ 目录 堆排序 第一种  ​编辑 第二种  TOP-K问题 建堆的时间复杂度 向下调整建堆的时间复杂度:  向上调整建堆的时间

    2024年01月21日
    浏览(54)
  • 数据结构进阶篇 之 【堆的应用】(堆排序,TOP-K问题)详细讲解

    所有人都关心我飞的高不高,只有我妈关心我翅膀硬不硬 1.1 建堆 1.2 利用堆删除思想来进行排序 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 学习一个知识,我们起码要直

    2024年04月10日
    浏览(46)
  • 【数据结构】—堆排序以及TOP-K问题究极详解(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波: ルミネセンス—今泉愛夏      

    2024年02月08日
    浏览(46)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(43)
  • 数据结构 | TOP-K问题

    TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。 就是从N个数里面找最大前K个(N远大于K) 思路一: N个数插入到堆里面,PopK次 时间复杂度是 O(N*logN) + K*logN == O(N*logN) N很大很大,假设N是100亿,K是10 100亿个整数大概需要40G左右 所以

    2024年02月05日
    浏览(41)
  • 数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K

            前言          逆水行舟,不进则退!!!                目录        认识堆        堆的创建         1,向下调整的方法建立堆         2,以向下调整的方式建立小根堆         3,向上调整的方式建堆        堆的插入        堆的删除              

    2024年02月04日
    浏览(53)
  • 【数据结构】堆的应用+TOP-K问题+二叉树遍历

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 该篇文章写到主要是:堆排序、 TOP-K问题、二叉树链式结构的实现、二叉树的遍历等等;如果有朋友还不太了解堆以及二叉树可以翻看我的上一篇博客:堆和二叉树的概念; 最

    2024年02月07日
    浏览(51)
  • 『初阶数据结构 • C语言』⑭ - C语言实现用堆解决 TOP-K 问题

    目录 TopK函数实现 如何测试 完整源码  生活中我们经常能见到TopK问题,例如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 所以, TopK问题即求出一组数据中前K个最大或最小的元素 ,一般情况下,数据量都比较大。 对于TopK问题,我们首先想到的可能是排序

    2024年02月16日
    浏览(41)
  • [数据结构 -- C语言] 堆实现Top-K问题,原来王者荣耀的排名是这样实现的,又涨知识了

    目录 1、什么是Top-K问题? 1.1 Top-K基本思路 2、Top-K问题逻辑分析 2.1 建堆,大小为K的小堆 2.2 将剩余的N - K 个元素依次与堆顶元素比较,大于就替换 2.3 打印堆 3、TopK实现代码 4、Top-K问题完整代码 结果展示: TopK问题的引入: 大家在玩王者荣耀的时候都遇到过xxx市第xxx某英雄

    2024年02月09日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包