【数据结构】（堆）Top-k|堆排序

目录

概念：

堆的实现 

构建

初始化

销毁

插入元素

往上调整 

删除堆顶元素 

往下调整 

返回堆顶元素 

 返回有效个数

是否为空

 堆排序

 Top-k问题

​编辑 创建数据

堆top-k

概念：

堆是将数据按照完全二叉树存储方式存储到一维数组中；

堆分为大堆和小堆：

大堆：父结点大于等于孩子结点；

小堆：父结点小于等于孩子结点；

父结点与（左右）孩子结点关系：

1.父结点 = （孩子结点-1）/2；

2.左结点= （父结点*2）+1；

        右结点= （父结点*2）+2；

堆的实现 

堆的逻辑结构是完全二叉树，物理结构是一维数组存储；

而独特的结点关系，堆排序也是一种选择排序，

构建

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* parr;
	int size;		//存储的有效数据个数
	int capacity;	//容量
}Heap;
//	用数组存储

初始化

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

销毁


//堆的销毁
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->parr);
	php->parr = NULL;
	php->size = php->capacity = 0;
	free(php);
	php = NULL;
}

插入元素

因为堆分为两类，在数据插入时，需要选择适应的调整；

以小堆来说：当插入一个新元素时，插入到堆尾，与父结点比较，相应的往上调整

//堆的插入元素
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//检查容量
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* newparr = (HPDataType*)realloc(php->parr, sizeof(HPDataType) * newcapacity);
		if (newparr == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->capacity = newcapacity;
		php->parr = newparr;
	}
	php->parr[php->size] = x;
	php->size++;
	
	//小堆
	//向上调整
	AdjustUp(php->parr, php->size - 1);
}

往上调整 

当插入一个新元素，按照孩子和父结点之间的关系进行比较，交换两结点数据，直到满足堆的性质 

//向上调整
void AdjustUp(HPDataType* parr,int size)
{
	int child = size;
	int parent = (child - 1) / 2;
	//小堆=> 父结点<=孩子结点
	while (child>0)
	{
		if (parr[child] < parr[parent])
		{
			//交换数据
			Swap(&parr[child], &parr[parent]);
			child = parent;        //更新结点位置
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

删除堆顶元素 

1.将堆顶元素和尾部元素互换位置；

2.将此刻不符合规定的堆顶元素往下调整至相应位置； 

// 删除堆顶（根节点）
void HeapPop(Heap* php)
{
	assert(php);
	//1.堆顶元素和尾部元素置换位置
	Swap(&php->parr[0], &php->parr[php->size - 1]);
	php->size--;	//删掉交换后的堆顶元素

	//2.将新站顶元素找到相应位置
	//向下调整
	AdjustDown(php->parr,php->size,0);
}

往下调整 

堆顶元素与其孩子结点比较，如何找到较大（较小）的孩子？

可以假设法：假设较大（较小）的孩子为左孩子，然后验证假设；

//向下调整
void AdjustDown(HPDataType* parr,int size,int parent)
{
	int child = (parent * 2) + 1;
	while (child<size)	//
	{
		//假设左孩子为较小值
		if (child+1<size && parr[child + 1] < parr[child])	//验证假设
		{
			++child;	//说明右孩子更小，更换孩子位置
		}
		//检查是否不符合堆排序结构 
		if (parr[parent] > parr[child])
		{
			Swap(&parr[parent], &parr[child]);
			//往下更新父结点 孩子结点位置
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

返回堆顶元素 

起始值为0；

//返回堆顶元素
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->parr[0];
}

 返回有效个数

注意，构建堆的时候，size是最后一个元素的下一个；

//返回堆内有效数据个数
size_t HeapSize(Heap* php)
{
	assert(php);

	return php->size;	//数组下标0开始
}

是否为空

//判断堆是否为空
bool HeapEmpty(Heap* php)
{
	return php->size == 0;
}

 堆排序

以上是一些堆的简单功能实现；算不上真正的堆排序；

假设给定一串数字，4,6,2,1,5,8,2,9；如何将其排序？比如升序；

  1. 建立一个大堆；
  2. 将堆顶元素与堆尾元素互换，且将遍历堆的范围-1，保证其想要的值保持不动；
  3. 将此刻不符合规定的堆顶往下调整，找到次大的值；重复步骤2；

其实相当于第一个元素默认是堆，后面的进行遍历调整； 

//排序,升序
void HeapSort(int* parr, int n)
{
	//1.建立大堆
	for (int i = 1;i < n; i++)
	{
		justUp(parr, i);
	}

	//2.堆顶元素与堆尾元素互换，然后将堆size-1（指只需要遍历到的位置）
	int end = n - 1;
	while (end>0)
	{
		//堆顶和堆尾 元素呼唤
		Swap(&parr[0], &parr[end]);
		//往下调整
		justDown(parr,end,0);
		end--;
	}
}

也有其他思路；

我们从下面子树往上遍历，而内部调整时往下调整

 n-1是最后结点下标值，（结点-1）/2 可以得到该结点的父结点，从父结点往下调整；

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

 Top-k问题

在排序的基础上，如果这个数很大呢，比如一百万个数，要找到前k个较大值；

此刻建堆排序显然不合适；

1.读取前K个值，建立其小堆；

2.依次读取后面的值，与堆顶比较：如果比堆顶大，替换堆顶进堆，再往下调整；

 创建数据

//tok-k 问题
//创建一千万的数据
void CreateNode()
{
	// 造数据
	int n = 10000000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 10000000;	//+i是 因为随机数产生只有三万个，加上i可以大大减少重复值
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

堆top-k

开辟K个数的空间（动态数组）；

建立K个数的小堆；

读取文件中值，遍历与堆顶比较，

void HeapTok(const char* file,int k)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	//开辟K个数的空间
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}

	//建立K个数的小堆
	for (int i = 0; i < k; i++)
	{
		//从文件流中 读取数据存到 开辟的空间中
		fscanf(fout,"%d", &minheap[i]);
		//往上调整
		AdjustUp(minheap, i);
	}

	//遍历文件数据 
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)	
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			//往下调
			AdjustDown(minheap, k, 0);
		}
	}

	//打印tok
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	free(minheap);
	fclose(fout);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/256958.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

python的argparse在celery中调用parser.parse_args()参数解析报错解决

python的argparse在celery中调用parser.parse_args()参数解析报错解决

文章目录 一、前言二、报错提示三、解决方案四、总结 一、前言 调用flask中的api接口&#xff0c;会调用我的异步函数&#xff0c;而异步函数是在celery框架中执行 下图的执行流程也没有问题 经过调试发现问题出在**parser.parse_args()**函数这里 二、报错提示 命令行运行…
阅读更多...
在Pytorch中自定义dataset读取数据

在Pytorch中自定义dataset读取数据

这里使用的是经典的花分类数据集 下载地址&#xff1a;https://storage.googleapis.com/download.tensorflow.org/example_images/flower_photos.tgz 下载结束后进行解压&#xff0c;可以得到五种不同种类花的图片&#xff0c;如上图所示 主函数 main def main():device tor…
阅读更多...
zookeeper：启动后占用8080端口问题解决

zookeeper：启动后占用8080端口问题解决

ZooKeeper是一个分布式的&#xff0c;开放源码的分布式应用程序协调服务。它为分布式应用提供一致性服务的软件&#xff0c;提供的功能包括&#xff1a;配置维护、域名服务、分布式同步、组服务等。 我们经常在运行zookeeper服务时&#xff0c;不需要配置服务端口&#xff0c;…
阅读更多...
二叉树的最大深度（LeetCode 104）

二叉树的最大深度（LeetCode 104）

文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一&#xff1a;深度优先搜索GolangC 方法二&#xff1a;广度优先搜索GolangC 参考文献 1.问题描述 给定一个二叉树 root &#xff0c;返回其最大深度。 叉树的「最大深度」是指从根节点到最远叶子节点的最长路径上的节…
阅读更多...
Apollo开放平台9.0让自动驾驶开发者轻松上手

Apollo开放平台9.0让自动驾驶开发者轻松上手

文章目录 平台架构&#xff1a;基础环境&#xff1a;开始使用&#xff1a;体验心得: 在自动驾驶技术飞速发展的今天&#xff0c;成为这个领域的一名开发者是一次挑战、一次冒险&#xff0c;更是一次心灵之旅。作为这个领域的先锋之一&#xff0c;Apollo开放平台9.0于12月19日发…
阅读更多...
TSINGSEE青犀边缘AI计算基于车辆结构化数据的车辆监控方案

TSINGSEE青犀边缘AI计算基于车辆结构化数据的车辆监控方案

随着人工智能技术的不断发展&#xff0c;边缘AI技术逐渐成为智能交通领域的研究热点。其中&#xff0c;基于边缘AI的车辆结构化数据技术与车辆监控系统是实现智能交通系统的重要手段之一。为了满足市场需求&#xff0c;TSINGSEE青犀边缘AI智能分析网关/视频智能分析平台推出了一…
阅读更多...
【百度PARL】强化学习笔记

【百度PARL】强化学习笔记

文章目录 强化学习基本知识一些框架Value-based的方法Q表格举个例子 强化的概念TD更新 Sarsa算法SampleSarsa Agent类 On_policy vs off_policy函数逼近与神经网络DQN算法DQN创新点DQN代码实现model.pyalgorithm.pyagent.py总结&#xff1a;举个例子 实战 视频&#xff1a;世界…
阅读更多...
【SQL】根据年月，查询月份中每一天的数据量

【SQL】根据年月，查询月份中每一天的数据量

传入YYYY-MM-01&#xff0c;查询这个月中每一天的数据量&#xff0c;没有数据的天数用0表示 WITH RECURSIVE DateRange AS (SELECT :startDate AS DateUNION ALLSELECT DATE_ADD(Date, INTERVAL 1 DAY) FROM DateRangeWHERE Date < LAST_DAY(:startDate) ) SELECTdr.Date,CO…
阅读更多...
docker中如何使用Arthas

docker中如何使用Arthas

docker中如何使用Arthas 一、操作步骤1、首先拷贝arthas包下来&#xff1a;2、其次选中你需要查看的容器ID&#xff1a;3、拷贝arthas程序包到容器目录下&#xff1a;4、进入到容器目录5、进入到第3步映射到容器的路径&#xff0c;并使用ll查看是否存在 arthas-boot.jar6、使用…
阅读更多...
全球移动通信（2G/3G/4G/5G）频谱分布情况

全球移动通信（2G/3G/4G/5G）频谱分布情况

一、概述 随着通信技术的不断发展&#xff0c;全球各国都在积极推进2G、3G、4G、5G网络的建设和应用。根据FCC统计&#xff0c;目前全球移动通信频谱分布如下&#xff1a; 二、分布 &#xff08;一&#xff09;俄罗斯 2G&#xff1a;主要使用900MHz和1800MHz两个频段。其中&…
阅读更多...
Postman接口测试之Postman常用的快捷键

Postman接口测试之Postman常用的快捷键

作为一名IT程序猿&#xff0c;不懂一些工具的快捷方式&#xff0c;应该会被鄙视的吧。收集了一些Postman的快捷方式&#xff0c;大家一起动手操作~ 简单操作 xc 请求 操作MAC系统windows系统请求网址 ⌘L Ctrl L 保存请求 ⌘S Ctrl S 保存请求为 ⇧⌘S Ctrl Shift S发送…
阅读更多...
云原生之深入解析Kubernetes集群发生网络异常时如何排查

云原生之深入解析Kubernetes集群发生网络异常时如何排查

一、Pod 网络异常 网络不可达&#xff0c;主要现象为 ping 不通&#xff0c;其可能原因为&#xff1a; 源端和目的端防火墙&#xff08;iptables, selinux&#xff09;限制&#xff1b; 网络路由配置不正确&#xff1b; 源端和目的端的系统负载过高&#xff0c;网络连接数满…
阅读更多...
如何搭建一个买衣服的微信小程序商城

如何搭建一个买衣服的微信小程序商城

随着移动互联网的普及&#xff0c;微信小程序商城已经成为众多商家开展线上业务的重要平台。本文将介绍如何搭建一个卖衣服的微信小程序商城&#xff0c;帮助您实现线上业务的拓展。 第一步&#xff1a;登录乔拓云平台进入商城后台管理页面 在浏览器中搜索乔拓云平台并登录&a…
阅读更多...
广汽本田售后服务技术技能竞赛总决赛

广汽本田售后服务技术技能竞赛总决赛

从2001年开始&#xff0c;广汽本田售后服务技术技能大赛年年举办&#xff0c;层层筛选、择优选拔&#xff0c;以赛促练全面提升服务领域一线人员的业务能力。 广汽本田售后服务技术技能大赛在赛程设置、考核内容和形式等方面进行了全面升级与强化&#xff0c;创新突破服务精英的…
阅读更多...
科士达新能源荣获CTC国检集团“产品碳足迹证书”

科士达新能源荣获CTC国检集团“产品碳足迹证书”

2023年12月14-15日&#xff0c;“2023光伏行业年度大会”在江苏省宿迁市召开&#xff0c;行业主管部门、行业组织、知名专家和光伏企业等代表莅临现场。科士达新能源受邀出席&#xff0c;并在同期举办的”光伏产品碳足迹与碳中和研讨会”上&#xff0c;荣获CTC国检集团“产品碳…
阅读更多...
WebMvcConfigurer接口详解及使用方式（Spring-WebMvc）

WebMvcConfigurer接口详解及使用方式（Spring-WebMvc）

简介 如下图所示WebMvcConfigurer是spring-webmvc jar包下的一个接口&#xff0c;spring-webmvc jar包又来源于spring-boot-starter-web&#xff0c;所以要使用WebMvcConfigurer要引入spring-boot-starter-web依赖。WebMvcConfigurer接口提供了常用的web应用拦截方法。通过实现…
阅读更多...
Elasticsearch 索引生命周期和翻滚 (rollover) 策略

Elasticsearch 索引生命周期和翻滚 (rollover) 策略

Elasticsearch 是搜索引擎中的摇滚明星&#xff0c;它的蓬勃发展在于使你的数据井井有条且速度快如闪电。 但当你的数据成为一场摇滚音乐会时&#xff0c;管理其生命周期就变得至关重要。 正确使用索引生命周期管理 (ILM) 和 rollover 策略&#xff0c;你的后台工作人员可确保顺…
阅读更多...
有损编码——Wyner-Ziv理论

有损编码——Wyner-Ziv理论

有损编码是一种在信息传输和存储中常见的编码技术&#xff0c;其主要目标是通过牺牲一定的信息质量&#xff0c;以换取更高的压缩效率。相比于无损编码&#xff0c;有损编码可以在保证一定程度的信息还原的前提下&#xff0c;使用更少的比特数来表示信息。Wyner-Ziv理论是一种重…
阅读更多...
台湾虾皮卖什么比较好

台湾虾皮卖什么比较好

虾皮&#xff08;Shopee&#xff09;平台在台湾地区广受欢迎&#xff0c;吸引了大量的消费者和卖家。该平台上有许多热销产品类别&#xff0c;这些产品在台湾市场上具有巨大的销售潜力。在本文中&#xff0c;我们将介绍虾皮平台上一些热门的产品类别&#xff0c;并提供一些建议…
阅读更多...
记录一次云服务器被攻击事件

记录一次云服务器被攻击事件

今天去登录华为云平台的时候&#xff0c;发现服务器的cpu涨到了百分之九十九&#xff0c;这个也太不正常了&#xff0c;我自己就只部署了一个页面&#xff0c;怎么会飚这么高呢&#xff1f; 然后&#xff0c;我就去找原因&#xff0c;使用top命令&#xff0c;去查看到底是谁占用…
阅读更多...
最新文章

Copyright @ 2022~2023