数据结构之堆排序以及Top-k问题详细解析

这篇具有很好参考价值的文章主要介绍了数据结构之堆排序以及Top-k问题详细解析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:点我进入主页

专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶

C语言刷题       数据结构初阶

欢迎大家点赞,评论,收藏。

一起努力

目录

1.前言

2.堆排序

2.1降序排序

2.2时间复杂度

3.Top-k问题

4.总结


1.前言

        在上一篇文章中我们主要讲解了关于大堆和小堆的代码实现,今天我们主要讲解关于堆排序以及堆排序的时间复杂度,我们会讲解关于经典的Top-k问题进行讲解(其中我会伪造一些数据来展示),今天的内容比上次的内容更加的爽,更有挑战性,其中的奥妙真的无法用语言来形容,接下来就让我们感受一下吧。

2.堆排序

        我们对数组进行降序排序,我们使用堆排序,在这里由于升序和降序的思想基本一致,只需要修改一些符号即可完成转化,所以我们只讲关于降序的内容。

2.1降序排序

        在上次的内容中我们使用向上调整来创建堆,我们是创建小堆还是大堆呢?我们想让数据进行降序,如果我们使用大堆的话堆的第一个数是最大的,我们取出来之后堆的顺序就乱了,我们需要重新进行大堆排序,那么我们的时间复杂度为O(n^2*logn),这比我们的冒泡排序还要慢,所以大堆是不可以的,所以我们选择小堆排序,我们这次依旧使用想上调整,详细代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
void Swap(int* num1, int* num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}
void print(int* arr, int size)
{
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
}
void AdJustUp(int* arr, int sz,int size)
{
	assert(arr);
	int child = sz, parent = (child - 1) / 2;
	while (child>0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
void AdJustDown(int* arr, int i, int size)
{
	assert(arr);
	int parent = i, child = 2 * parent + 1;
	while (child<size)
	{
		if (child + 1 < size && arr[child] >arr[child + 1])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}
void HeapSort(int* arr, int n)
{
	assert(arr);
	for (int i = 0; i < n; i++)
	{
		AdJustUp(arr, i, n);
	}
	for (int i = 0; i < n-1; i++)
	{
		Swap(&arr[0], &arr[n - 1 - i]);
		AdJustDown(arr, 0, n - 1 - i);
	}

}
int main()
{
	int arr[10];
	int n = 10;
	for (int i = 0; i < n; i++)
	{
		arr[i] = i;
	}
	HeapSort(arr,n);
	print(arr, n);
	return 0;
}

我们的运行结构如下:

数据结构之堆排序以及Top-k问题详细解析,数据结构

事实上我们这不是我们的堆排序,真正的堆排序在第一次创建小堆时代码为:

		for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(arr, i, n);
	}

向下调整为什么可以实现呢?,我们知道向下调整是左边和右边都是小堆然后根节点是新插入的我们就可以利用向下调整进行排序,那我们在最后一个节点的父节点进行向下调整,让他们都成为小堆,这样我们就可以完成小堆的创建。那为什么采用这种形式呢?仅仅是因为代码少吗?事实上这与我们的时间复杂度有关。

2.2时间复杂度

        我们看利用向上调整建立小堆的时间复杂度,我们第k层有2^(k-1)个节点,每个节点需要向上调整k-1次共调整(k-1)*2^(k-1)次,第k-1层有2^(k-2),每个节点需要调整k-2次,共调整(k-2)*2^(k-2)……第二层有2^1个节点,每个节点需要调整1次,第一层有2^0个节需要调整0次,共需要调整T(k)=0*2^0+1*2^1+……+(k-2)*2^(k-2)+(k-1)*2^(k-1),我们化简可以得到T(k)=(k-2)2^k+2;其中k=logN,所以T(k)=NlogN;但是我们采用向下调整我们第k层有我们第k层有2^(k-1)个节点,每个节点需要向上调整0次共调整0*2^(k-1)次,第k-1层有2^(k-2),每个节点需要调整1次,共调整1*2^(k-2)……第二层有2^1个节点,每个节点需要调整k-2次,第一层有2^0个节需要调整k-1次,共需要调整T(k)=(k-1)*2^0+(k-2)*2^1+……+1*2^(k-2)+0*2^(k-1),我们化简得到T(k)=2^k-k-1,其中k=logN,故T(k)=N-logN;可以看到向下调整建立堆时间复杂度低,所以我们选择向下调整这大大减少了我们的运算时间。

3.Top-k问题

        有一个问题是我们在一组数中(共N个数)找到最小的k个数,其中N远大于k,让我们找到前k个数,当数据很小的时候我们利用堆排序进行查找很容易,但是当数据量特别大的时候我们就很难实现,因为数据占用的内存太大了,例如我们要在1百亿个数据中找到前10个最小的数,100万个整形数据相当于占用37GB,这样我们就很难处理,这时候就出现了我们的Top-k问题,我们是如何解决这个问题呢?这时候我们由于需要找最小的前10个数据我们创建一个大堆,然后输入一个数据就将堆顶元素替换然后再向下调整这样就可以找到最小的10个数据,我们创建100万个数据进行模拟,我们的代码如下:

我们将数据放在文件中,生成data.txt文件

#include<stdio.h>
int main()
{
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("fopen fail");
		return 1;
	}
	for (int i = 0; i < 1000000; i++)
	{
		fprintf(pf,"%d\n", i);
	}
	fclose(pf);
	pf = NULL;
	return 0;
}

修改其中的10个数据让他成为我们的结果,然后进行下一步找到这k个数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int MyHeapData;
typedef struct Heap {
	MyHeapData* data;
	int size;
	int capacity;
}Heap;
void HeapInit(Heap* php)
{
	assert(php);
	php->data = (MyHeapData*)malloc(sizeof(MyHeapData)*10);
	php->size = 0;
}
void Swap(int* num1, int* num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}
void AdJustDown(int* arr, int n, int i)
{
	assert(arr);
	int parent = 0, child = 2 * parent + 1;
	while (child<n)
	{
		if (child+1<n&&arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[parent] < arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
void AdJustUp(MyHeapData* arr, int size)
{
	assert(arr);
	int child = size - 1, parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
int main()
{
	//FILE* pf = fopen("data.txt", "w");
	//if (pf == NULL)
	//{
	//	perror("fopen fail");
	//	return 1;
	//}
	//for (int i = 0; i < 1000000; i++)
	//{
	//	fprintf(pf,"%d\n", i);
	//}
	//fclose(pf);
	//pf = NULL;
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("fopen fail");
		return 1;
	}
	int data;
	int i;
	Heap ph ;
	HeapInit(&ph);
	for (i = 0; i < 10; i++)
	{
		fscanf(pf, "%d", &data);
		ph.data[i] = data;
		AdJustUp(ph.data, i);
	}
	while (fscanf(pf, "%d", &data) != EOF)
	{
		if(data<ph.data[0])
			Swap(&data, &ph.data[0]);
		AdJustDown(ph.data, 10, 0);
	}
	for (i = 0; i < 10; i++)
	{
		printf("%d ", ph.data[i]);
	}
	fclose(pf);
	pf = NULL;
	return 0;
}

运行结果如下:

数据结构之堆排序以及Top-k问题详细解析,数据结构

这就是我们经典的Top-k问题;

4.总结

        今天的内容到这里就结束了,希望大家可以好好的理解今天的内容,欢迎大家来三连。文章来源地址https://www.toymoban.com/news/detail-752869.html

到了这里,关于数据结构之堆排序以及Top-k问题详细解析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题

    目录 堆的概念及结构 ​编辑 堆的实现  实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据  交换 堆的插入(插入最后) 向上调整(这次用的是小堆) 堆的删除(删除根) 向下调整(这次用的小堆) 堆排序 TOP-K问题 如果有一个关键码的集合 K = { , , , …

    2024年02月05日
    浏览(50)
  • 数据结构-堆的实现及应用(堆排序和TOP-K问题)

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

    2024年02月07日
    浏览(49)
  • 【数据结构】二叉树-堆(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日
    浏览(53)
  • 数据结构进阶篇 之 【堆的应用】(堆排序,TOP-K问题)详细讲解

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

    2024年04月10日
    浏览(45)
  • 数据结构(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日
    浏览(39)
  • 数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K

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

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

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

    2024年02月07日
    浏览(50)
  • 『初阶数据结构 • 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

领红包