二叉树堆的应用实例分析:堆排序 | TOP-K问题


在这里插入图片描述

📷 江池俊: 个人主页
🔥个人专栏: ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人,再渺小也不会迷途。


在这里插入图片描述

文章目录

    • 前言
    • 一、堆排序
      • 1.1 排序思想
      • 1.2 堆排序过程(图解)
      • 1.3 堆排序代码(升序为例)
    • 二、TOP-K问题
      • 2.1 TOP-K问题思路
      • 2.2 随机生成随机数并存入文件
      • 2.3 建小堆取前 k 个最大的数

前言

在学习堆排序和TOP-K问题之前,大家需要先熟悉两个算法(即 向上调整向下调整 算法),这两大算法可谓是它们的核心。话不多说,我们直接上手。

一、堆排序

注意:当要求排序为升序,在建堆时需要建成大堆,反过来当要求降序,在建堆时就需要建成小堆。


1.1 排序思想

堆排序是一种有效的排序算法,它的 核心思想将一个无序数组构建成一个大顶堆(或小顶堆),然后将堆顶元素(最大值或最小值)与堆尾元素互换,之后将剩余的元素重新调整为大顶堆(或小顶堆),以此类推,直到整个数组有序。

  • 当要求排序为升序时,我们希望输出的结果是 从小到大。为了满足这个需求,在建堆时需要将较大的元素放在堆顶,这样在每次交换后,最大的元素会被放在数组的最后面。因此,在建堆过程中需要将数组建成大顶堆。
  • 相反,当要求排序为降序时,我们希望输出的结果是 从大到小。为了满足这个需求,在建堆时需要将较小的元素放在堆顶,这样在每次交换后,最小的元素会被放在数组的最后面。因此,在建堆过程中需要将数组建成小顶堆。

这里我们以升序为例,如图:

在这里插入图片描述


1.2 堆排序过程(图解)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

1.3 堆排序代码(升序为例)

typedef int HPDataType

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 (parent >= 0)
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
			//child = (child - 1) / 2;
			//parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		// 假设左孩子小,如果假设错了,更新一下
		if (child + 1 < size && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序 --- 升序
void HeapSort(int* a, int n)
{
	//建大堆
	//向上调整建对堆0(N*logN)
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/

	//向下调整建堆
	// (找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整)0(N)
	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;
	}

}

在这里插入图片描述



二、TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。


2.1 TOP-K问题思路

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

  1. 用数据集合中前K个元素来建堆
    • 前k个最大的元素,则建小堆
    • 前k个最小的元素,则建大堆
  2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
    • 将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

2.2 随机生成随机数并存入文件

//产生一千万个随机数
void CreateNDate()
{
	// 造数据
	int n = 10000000;
	srand(time(0)); //srand()最多产生三万多个随机数
	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() + i) % 10000000; //+i减少随机数的重复
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

【运行结果】:
生成 0~9999999 的随机数
在这里插入图片描述

2.3 建小堆取前 k 个最大的数

将 “data.txt” 文件中的数据依次读取建小堆,最后堆中的数据就是文件中最大的前 k 个数。

//向上调整 --- 小堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
			//child = (child - 1) / 2;
			//parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		// 假设左孩子小,如果解设错了,更新一下
		if (child + 1 < size && a[child + 1] < a[child])
		{
			++child;
		}

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

// 取前k个最大的数
void PrintTopK(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);
	}
	
	//读取所有数据,建成小堆,最大的前k个数据就在堆中
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	free(minheap);
	fclose(fout);
}

运行结果:

在这里插入图片描述
【打开文件修改数据,测试程序正确性】:
在这里插入图片描述
在这里插入图片描述

修改数据后的运行结果:

在这里插入图片描述


🔥💖以上TOP-K问题只是取前k个最大数据的例子,取前k个最小数据与此类似,这里博主就不再赘述,希望这篇文章能够帮到大家,期待大家的三连支持🤞

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

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

相关文章

C++ 数论相关题目(欧拉函数、筛法求欧拉函数)

1、欧拉函数 给定 n 个正整数 ai &#xff0c;请你求出每个数的欧拉函数。 欧拉函数的定义 1∼N 中与 N 互质的数的个数被称为欧拉函数&#xff0c;记为 ϕ(N) 。 若在算数基本定理中&#xff0c;Npa11pa22…pamm &#xff0c;则&#xff1a; ϕ(N) Np1−1p1p2−1p2…pm−1p…

【数学建模】插值与拟合

文章目录 插值插值方法用Python解决插值问题 拟合最小二乘拟合数据拟合的Python实现 适用情况 处理由试验、测量得到的大量数据或一些过于复杂而不便于计算的函数表达式时&#xff0c;构造一个简单函数作为要考察数据或复杂函数的近似 定义 给定一组数据&#xff0c;需要确定满…

b+树的理解

二叉树&#xff1a; 每个节点支持两个分支的树结构&#xff0c;相比于单向链表&#xff0c;多了一个分支。 二叉查找树&#xff1a; 在二叉树的基础上增加了一个规则&#xff0c;左子树的所有节点都小于它的根节点&#xff0c;右子树的所有节点都大于他的根节点。 二叉查找树…

Flutter中实现中国省份地图

效果展示(这里只展示局部&#xff0c;完全展示违规)&#xff1a; 可以点击省份改变颜色&#xff0c;更多功能可以自行拓展。 注&#xff1a;非完整中国地图&#xff01;&#xff01;&#xff01; 本文用于记录在Flutter项目中安卓端实现中国地图&#xff0c;因为实现过程是通过…

分类预测 | Matlab实现GRU-Attention-Adaboost基于门控循环单元融合注意力机制的Adaboost数据分类预测/故障识别

分类预测 | Matlab实现GRU-Attention-Adaboost基于门控循环单元融合注意力机制的Adaboost数据分类预测/故障识别 目录 分类预测 | Matlab实现GRU-Attention-Adaboost基于门控循环单元融合注意力机制的Adaboost数据分类预测/故障识别分类效果基本描述程序设计参考资料 分类效果 …

【Linux C | 进程】Linux 进程间通信的10种方式(2)

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

手写一个图形验证码

文章目录 需求分析 需求 使用 JS 写一个验证码&#xff0c;并在前端进行校验 分析 新建文件 VueImageVerify.vue <template><div class"img-verify"><canvas ref"verify" :width"state.width" :height"state.height&qu…

OpenCV-Python(51):基于Haar特征分类器的面部检测

目标 学习了解Haar 特征分类器为基础的面部检测技术将面部检测扩展到眼部检测等。 基础 以Haar 特征分类器为基础的对象检测技术是一种非常有效的对象检测技术(2001 年Paul_Viola 和Michael_Jones 提出)。它是基于机器学习的,通过使用大量的正负样本图像训练得到一个cascade_…

socket以及字节序

1. socket 介绍&#xff1a; 简介&#xff1a; 所谓 socket&#xff08; 套接字&#xff09;&#xff0c;就是对网络中不同主机上的应用进程之间进行双向通信的 端点的抽象。 一个套接字就是网络上进程通信的一端&#xff0c;提供了应用层进程利用网络协议交换数据的机制。从所…

推荐一个还可以的windows ssh工具

1.下载 https://github.com/kingToolbox/WindTerm/releases 2.解压 3.使用 上传 下载都很快 比cmd窗口好用 当然和finalshell有点像

Linux编辑器vim(含vim的配置)

文章目录 前言vim的基本概念vim基本操作进入vim模式切换退出vim vim指令vim命令模式指令vim底行模式命令 简单vim配置 前言 本篇文章&#xff0c;小编将介绍Linux编辑器–>vim以及vim的配置。 vim的基本概念 正常/普通/命令模式(Normal mode) 控制屏幕光标的移动&#xf…

云贝教育 |【分享课】1月25日Oracle分享主题:Oracle 单实例DG

分享主题&#xff1a;Oracle 19c 单实例DG-1 讲师&#xff1a;刘峰 直播时间&#xff1a;1月25日周四19:30 直播平台&#xff1a;微信视频号 云贝学院

(更新)“高铁开通”地级市-多期DID工具变量(2000-2022年)

参照卞元超&#xff08;2019&#xff09;、邓慧慧&#xff08;2020&#xff09;、汪克亮&#xff08;2021&#xff09;等人做法&#xff0c;将开通高铁的城市作为处理组&#xff0c;未开通高铁的城市作为对照组。地级市开通高铁之后的DID赋值为1&#xff0c;未开通则赋值为0 一…

云计算中的出口数据是指什么?

谷歌云&#xff08;Google Cloud&#xff09;近日宣布了一项重大政策变动&#xff0c;决定免除那些选择终止使用其服务并将数据迁移到其他云服务商或本地环境的客户的出口数据费用&#xff08;数据导出费用&#xff09;。 这一举措由谷歌云平台负责人阿米特扎维里&#xff08;A…

docker 基础手册

文章目录 docker 基础手册docker 容器技术镜像与容器容器与虚拟机docker 引擎docker 架构docker 底层技术docker 二进制安装docker 镜像加速docker 相关链接docker 生态 docker 基础手册 docker 容器技术 开源的容器项目&#xff0c;使用 Go 语言开发原意“码头工人”&#x…

SpringBoot责任链与自定义注解:优雅解耦复杂业务

引言 责任链模式是一种行为设计模式&#xff0c;它允许你将请求沿着处理者链进行传递&#xff0c;直到有一个处理者处理请求。在实际应用中&#xff0c;责任链模式常用于解耦发送者和接收者&#xff0c;使得请求可以按照一定的规则被多个处理者依次处理。 首先&#xff0c;本…

【LeetCode】104. 二叉树的最大深度(简单)——代码随想录算法训练营Day16

题目链接&#xff1a;104. 二叉树的最大深度 题目描述 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例…

Docker网络配置与自定义IP容器通信

目录 前言 一、docker网络配置 1. bridge 虚拟网桥 2. host 网络模式 3. none 网络模式 4. 自定义container网络模式 二、自定义IP容器通信 1. 自定义IP 2. 创建所需容器&#xff08;mysql&#xff0c;tomcat&#xff09; 3. 准备项目资源 4. 构建Nginx实现负载均衡…

垃圾回收小程序:环保与便捷的完美结合

一、引言 随着科技的发展&#xff0c;移动应用程序已经成为人们日常生活中不可或缺的一部分。其中&#xff0c;废品回收小程序以其独特的价值和功能&#xff0c;日益受到人们的关注和青睐。本文将探讨废品回收小程序开发的重要性、功能特点、技术实现和未来发展趋势。 二、废…

AOP切面

什么是Spring的AOP AOP在spring中又叫“面向切面编程”&#xff0c;它可以说是对传统我们面向对象编程的一个补充&#xff0c;从字面上顾名思义就可以知道&#xff0c;它的主要操作对象就是“切面”&#xff0c;所以我们就可以简单的理解它是贯穿于方法之中&#xff0c;在方法…