【数据结构】堆的实现及TOP-K问题

文章目录

  • 前言
  • 1. 堆的概念及结构
  • 2. 堆的实现
    • 2.1 堆向上调整算法
    • 2.2 堆向下调整算法
    • 2.3 堆的创建
    • 2.4 堆的删除
    • 2.5 堆的常用接口代码实现
  • 3. 堆的应用
    • TOP-K问题

 
 

前言

在正式讲堆之前，我们要先来讲一下二叉树的顺序结构：

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
在这里插入图片描述

 
 

1. 堆的概念及结构

如果有一个关键码的集合K = { k k k0， k k k1， k k k2，… ， k k kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： K K Ki <= K K K2*i+1 且 K K Ki <= K K K2*i+2（ K K Ki >= K K K2*i+1 且 K K Ki >= K K K2*i+2） i = 0，1，2，… ，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆的性质：

堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一颗完全二叉树。

在这里插入图片描述

来看几道题：

1.下列关键字序列为堆的是：（）
A 100, 60, 70, 50, 32, 65
B 60, 70, 65, 50, 32, 100
C 65, 100, 70, 32, 50, 60
D 70, 65, 100, 32, 50, 60
E 32, 50, 100, 70, 65, 60
F 50, 100, 70, 65, 60, 32
2.已知小根堆为8, 15, 10, 21, 34, 16, 12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。
A 1
B 2
C 3
D 4
3.一组记录排序码为(5 11 7 2 3 17), 则利用堆排序方法建立的初始堆为
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)
4.最小堆[0, 3, 2, 5, 7, 4, 6, 8], 在删除堆顶元素0之后，其结果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]

// 答案
1.A
2.C
3.C
4.C

 
 

2. 堆的实现

在讲堆的实现之前，我们要先来理解一下，堆是一个很讲究的数据结构，设计得是非常美妙的：
在这里插入图片描述

 

2.1 堆向上调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从最后一个孩子节点开始的向上调整算法可以把它调整成一个大堆。
在这里插入图片描述
讲了这些，我们用代码来实现一下这个过程：

// 向上调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void AdjustUp(HPDataType* a, int child, int (*compare)(const void*, const void*)) 
{
	assert(a);
	int parents = (child - 1) / 2; //找到孩子节点的父节点
	while (child > 0)
	{
		if (compare(&a[parents], &a[child]) > 0)  // 通过用户自己写的一个函数来判断是建大堆还是小堆
		{
			Swap(&a[child], &a[parents]);
			// 调整孩子节点和父节点的位置
			child = parents;
			parents = (child - 1) / 2;
		}
		else 
			break;
	}
}

这就是我们向上调整算法的实现，但相比较于向下调整算法，向上调整的效率还是比较低的，所以我们重点掌握向下调整算法就行了。

 

2.2 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
在这里插入图片描述

我们用代码来实现一下这个逻辑：

// 向下调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void  AdjustDown(HPDataType* a, int parents, int size, int (*compare)(const void*, const void*))
{
	assert(a);
	int child = parents * 2 + 1; // 先将左孩子设置为孩子节点
	while (child < size)
	{
		// 这里我们以建大堆为例
		if (child + 1 < size && compare(&a[child], &a[child + 1]) > 0) 
		{
			// 比较左孩子和右孩子,如果右孩子比左孩子大,就将孩子节点++
			child++;
		}
		if (compare(&a[parents], &a[child]) > 0) // 如果父亲节点小于孩子节点,就进行交换
		{
			Swap(&a[parents], &a[child]);
			// 调整孩子节点和父节点的位置
			parents = child;
			child = parents * 2 + 1;
		}
		else
			break;
	}
}

 

2.3 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = { 1,5,3,8,7,6 };

在这里插入图片描述

 

2.4 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述

 

2.5 堆的常用接口代码实现

// 交换
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

// 向上调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void AdjustUp(HPDataType* a, int child, int (*compare)(const void*, const void*)) 
{
	assert(a);
	int parents = (child - 1) / 2; //找到孩子节点的父节点
	while (child > 0)
	{
		if (compare(&a[parents], &a[child]) > 0)  // 通过用户自己写的一个函数来判断是建大堆还是小堆
		{
			Swap(&a[child], &a[parents]);
			// 调整孩子节点和父节点的位置
			child = parents;
			parents = (child - 1) / 2;
		}
		else 
			break;
	}
}

// 向下调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void  AdjustDown(HPDataType* a, int parents, int size, int (*compare)(const void*, const void*))
{
	assert(a);
	int child = parents * 2 + 1; // 先将左孩子设置为孩子节点
	while (child < size)
	{
		// 这里我们以建大堆为例
		if (child + 1 < size && compare(&a[child], &a[child + 1]) > 0) 
		{
			// 比较左孩子和右孩子,如果右孩子比左孩子大,就将孩子节点++
			child++;
		}
		if (compare(&a[parents], &a[child]) > 0) // 如果父亲节点小于孩子节点,就进行交换
		{
			Swap(&a[parents], &a[child]);
			// 调整孩子节点和父节点的位置
			parents = child;
			child = parents * 2 + 1;
		}
		else
			break;
	}
}



// 堆的构建
void HeapCreate(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_size = hp->_capacity = 0;
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_size = hp->_capacity = 0;
}

// 堆的打印
void HeapPrint(Heap* hp)
{
	assert(hp);
	int i = 0;
	for (i = 0;i < hp->_size;i++)
	{
		printf("%d ", hp->_a[i]);
	}
}


// 堆的插入
void HeapPush(Heap* hp, HPDataType x, int (*compare)(const void*, const void*))
{
	assert(hp);
	//扩容
	if (hp->_size == hp->_capacity)
	{
		int newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}

	// 插入
	hp->_a[hp->_size] = x;
	// 向上调整
	AdjustUp(hp->_a, hp->_size, compare);

	hp->_size++;
}

// 堆的删除
void HeapPop(Heap* hp, int (*compare)(const void*, const void*))
{
	assert(hp);
	assert(hp->_a);
	assert(hp->_size >= 0);

	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	// 向下调整
	AdjustDown(hp->_a, 0, hp->_size, compare);

}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	return hp->_a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
	return hp->_size;
}

// 堆的判空
int HeapEmpty(Heap* hp)
{
	return hp->_size == 0;
}

 
 

3. 堆的应用

TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

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

  1. 用数据集合中前K个元素来建堆

    • 前K个最大的元素，则建小堆
    • 前K个最小的元素，则建大堆

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

我们先写一个程序来创建一亿个数的程序，然后我在创建出来的文件中，随机修改了十个数，把他们改得都很大，因为我也不知道我是在哪些地方改的所以就不展示了：

void CreateNDate()
{
	int num = 100000000;
	int i = 0;
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("fopen");
		exit(-1);
	}
	for (i = 0;i < num;i++)
	{
		fprintf(pf, "%d\n", rand() % 100000000);
	}


	fclose(pf);
}

int main()
{
	//创建一个含有一亿个数字的文件
	srand((unsigned int)time(NULL));
	CreateNDate();

	return 0;
}

在这里插入图片描述

接下来我们就来试试吧：

//建堆时,根据该函数来决定大堆还是小堆
int CreakSmallHeap(const void* x, const void* y)
{
	return *(int*)x - *(int*)y;
}

void PrintTopK(int k)
{
	// 定义一个堆结构来存放数据
	Heap hp;
	// 堆的大小取决于我们要找的前k个数
	hp._a = (HPDataType*)malloc(sizeof(HPDataType) * k);
	if (hp._a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	hp._capacity = k;
	hp._size = 0;

	//打开文件
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("fopen fail");
		exit(-1);
	}

	//用前k个数建堆
	int i = 0;
	for (i = 0;i < k;i++)
	{
		int a = 0;
		fscanf(pf, "%d", &a);
		HeapPush(&hp, a, CreakSmallHeap);
	}

	//遍历文件,比堆头大的数就进堆,并向下调整
	while (fscanf(pf, "%d", &i) != EOF)
	{
		if (i > hp._a[0])
		{
			hp._a[0] = i;
			AdjusutDown(hp._a, 0, k, CreakSmallHeap);
		}
	}

	for (i = 0;i < k;i++)
	{
		printf("%d ", hp._a[i]);
	}
	printf("\n");
	//销毁栈
	HeapDestory(&hp);
	//关闭文件
	fclose(pf);
}
int main()
{
	创建一个含有一亿个数字的文件
	//srand((unsigned int)time(NULL));
	//CreateNDate();

	PrintTopK(10);

	return 0;
}

结果如下：

在这里插入图片描述
还有一个问题：
可能有人不知道为什么我们找最大的前几个数为什么要建小堆，难道不能建大堆，然后将后面取到的数与堆的最后一个数比较吗？原因是：
在这里插入图片描述

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

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

相关文章

认识机器学习【woodwhales.cn】

认识机器学习【woodwhales.cn】

为了更好的阅读体验&#xff0c;建议移步至笔者的博客阅读&#xff1a;认识机器学习 生活中的问题1&#xff1a;居民家庭生活用气价格 北京燃气小程序在线咨询&#xff0c;查询北京居民家庭生活用气价格 上图价格梯度&#xff0c;可以由文字转换成表格&#xff1a; 第一档用气…
阅读更多...
【Matlab】LSTM长短期记忆神经网络时序预测算法（附代码）

【Matlab】LSTM长短期记忆神经网络时序预测算法（附代码）

资源下载&#xff1a; https://download.csdn.net/download/vvoennvv/88688439 一&#xff0c;概述 LSTM&#xff08;Long Short-Term Memory&#xff09;是一种常用的循环神经网络&#xff08;Recurrent Neural Network&#xff0c;RNN&#xff09;结构&#xff0c;由于其对于…
阅读更多...
UI自动化Selenium 显式和隐式等待Wait

UI自动化Selenium 显式和隐式等待Wait

一、问题现象 大家是否自动化执行过程中&#xff0c;出现脚本时而成功时而失败的情况&#xff1b;发现常见情况如下&#xff1a; 1、元素时而出现时而提示不存在&#xff0c;timeout 2、元素时而可以操作时而不能操作&#xff1b;提示&#xff1a;元素不可点击或不可操作 3…
阅读更多...
Qdrant向量数据库

Qdrant向量数据库

Qdrant 是专为扩展过滤支持而设计的向量相似度搜索引擎和向量数据库&#xff0c;这使得它适用于各种基于神经网络的语义匹配、图像搜索等应用。 Qdrant 使用 Rust &#x1f980; 编写&#xff0c;即使在高负载下也能快速、可靠地工作。 Qdrant架构 上图展示了 Qdrant 一些主要…
阅读更多...
【排序】堆排序（C语言实现）

【排序】堆排序（C语言实现）

文章目录 前言1. 堆排序1.1 堆排序的思想1.2 堆排序的实现 2. 为什么向下调整而不是向上调整 前言 本章主要会讲堆排序的实现过程以及向上调整和向下调整的时间复杂度&#xff0c;在学习本章前&#xff0c;需要对堆、以及向上调整和向下调整有一个了解&#xff0c;如果不了解的…
阅读更多...
【CISSP学习笔记】5. 安全架构和工程

【CISSP学习笔记】5. 安全架构和工程

该知识领域涉及如下考点&#xff0c;具体内容分布于如下各个子章节&#xff1a; 使用安全设计原理来研究、实施与管理工程过程理解安全模型的基本概念&#xff08;例如 Biba、Star Model、Bell-LaPadula 等模型&#xff09;基于系统安全要求选择控制措施理解信息系统 (IS) 的安…
阅读更多...
Nginx多ip部署多站点

Nginx多ip部署多站点

目录 1.修改网卡配置信息 2.修改主要配置文件nginx.conf 1.修改网卡配置信息 1)来到网卡配置文件存放目录下 cd /etc/sysconfig/network-scripts/ 2)对 ifcfg-ens33 文件进行配置修改前先进行备份 cp ifcfg-ens33 ifcfg-ens33.default 3)先修改成最小配置&#xff0c;使用 d…
阅读更多...
QT音频编程实战项目（二）

QT音频编程实战项目（二）

接上一篇 我们在实现完槽函数的定义后&#xff0c;我们应该将这些槽函数和对应的信号连接起来 接着将每个控件都对应转到槽进行实现&#xff1a; 这个是对打开文件呢个控件转到槽的具体操作&#xff1a; 首先通过QDir::homePath()获得用户的主目…
阅读更多...
CCNP课程实验-05-Comprehensive_Experiment

CCNP课程实验-05-Comprehensive_Experiment

目录 实验条件网络拓朴 基础配置实现IGP需求&#xff1a;1. 根据拓扑所示&#xff0c;配置OSPF和EIGRP2. 在R3上增加一个网段&#xff1a;33.33.33.0/24 (用Loopback 1模拟) 宣告进EIGRP&#xff0c;并在R3上将EIGRP重分布进OSPF。要求重分布进OSPF后的路由Tag值设置为666&…
阅读更多...
java工作流详解

java工作流详解

什么是工作流&#xff1f; 工作流&#xff1a;两个或两个以上的人&#xff0c;为了共同的目标&#xff0c;连续的以串行或并行的方式去完成某一业务。 业务&#xff1a;工作流所指业务涵盖了与经营相关的活动。 串行或并行&#xff1a;业务中的步骤也许以一步接着一步的方式…
阅读更多...
YOLOv8改进：IoU系列篇 | Shape-IoU关注边界框本身的形状和尺度来计算损失 | 2023年12月最新IoU改进

YOLOv8改进：IoU系列篇 | Shape-IoU关注边界框本身的形状和尺度来计算损失 | 2023年12月最新IoU改进

🚀🚀🚀本文改进： 提出了一种新颖的Shape-IoU，小目标检测实现涨点，更加关注边界框本身的形状和尺度来计算损失 🚀🚀🚀YOLOv8改进专栏：http://t.csdnimg.cn/hGhVK 学姐带你学习YOLOv8，从入门到创新，轻轻松松搞定科研； 1.Shape-IoU原理介绍 论文：https://ar…
阅读更多...
【ps】如何给人偶添加衣服

【ps】如何给人偶添加衣服

使用PS工具扣出人物 使用编辑-变形-操控变型 、
阅读更多...
Vue3-27-路由-路径参数的简单使用

Vue3-27-路由-路径参数的简单使用

什么是路径参数 在路由配置中&#xff0c;可以将【参数】放在【路由路径】中&#xff0c; 从而实现&#xff0c;同一个 路由&#xff0c;同一个组件&#xff0c;因路径参数不同&#xff0c;可以渲染出不同的内容。特点 &#xff1a; 1、当携带不同路径参数的路由相互跳转时&am…
阅读更多...
Django Cookie和Session使用（十一）

Django Cookie和Session使用（十一）

一、Cookie Cookie具体指一小段信息&#xff0c;它是服务器发送出来存储在浏览器上的一组键值对&#xff0c;下次访问服务器时浏览器会自动携带这些键值对&#xff0c;以便服务器提取有用信息。 Cookie的特性 1、服务器让浏览器进行设置的 2、保存在浏览器本地&#xff0c;…
阅读更多...
二叉搜索树介绍以及实现

二叉搜索树介绍以及实现

二叉树无论是在实际运用还是面试题中&#xff0c;都是一种十分热门的数据结构&#xff0c;而二叉搜索树则是进阶版的二叉树&#xff0c;在map和set中也有应用。 什么是二叉搜索树 二叉搜索树又叫二叉排序树&#xff0c;它可以是一颗空树&#xff0c;又或者是有以下三个特点的…
阅读更多...
用简单的方式理解串行主从通信方式（适用于LEU与TCC等外部设备之间的通信）

用简单的方式理解串行主从通信方式（适用于LEU与TCC等外部设备之间的通信）

串行通信方式 数据按位序传送&#xff0c;最少需要两根通道&#xff08;如RS485、CAN总线、以太网&#xff09;。 优点&#xff1a;成本低&#xff0c;适合远距离通信。 缺点&#xff1a;速度慢、效率低。 注&#xff1a;以上特征为相较于并行通信方式。 主从通信方式 以RS4…
阅读更多...
skimage图像处理（全）

skimage图像处理（全）

文章目录 一、简介二、安装三、模块简介&#xff1a;API reference四、项目实战4.1、2D图像处理4.1.1、打印图像属性4.1.2、读取 / 显示 / 保存图像&#xff1a;skimage.io.imread() skimage.io.imshow() skimage.io.imsave()4.1.3、颜色空间转换&#xff1a;skimage.color.r…
阅读更多...
轻松搞定软件开发：找对软件开发公司的流程与注意事项!

轻松搞定软件开发：找对软件开发公司的流程与注意事项!

随着数字化时代的来临&#xff0c;软件开发在企业和个人生活中扮演着越来越重要的角色&#xff0c;然而&#xff0c;如何找到一家合适的软件开发公司却成为了一个令人头疼的问题。 本文将为你详细解读找软件开发公司的流程&#xff0c;以及在选择过程中需要注意的事项&#xf…
阅读更多...
十大排序的个人总结之——冒泡排序、插入排序

十大排序的个人总结之——冒泡排序、插入排序

同样&#xff0c;这两几乎也是被淘汰了的算法&#xff0c;尽管它们是稳定的&#xff0c;但是时间复杂度没人喜欢&#xff0c;了解一下就好&#xff0c;没啥好说的&#xff0c;注意最后一句话就行了 一&#xff0c;冒泡排序 1. 算法步骤 共n-1趟&#xff0c;谁两敢冒泡就换了…
阅读更多...
C++ 不能用作全局变量名或给定 C 语言的链接

C++ 不能用作全局变量名或给定 C 语言的链接

错误&#xff1a; C 不能用作全局变量名或给定 C 语言的链接 解决方案&#xff1a; 先抽自己两巴掌。 问问自己main函数作为一个函数&#xff0c;后面有没有添加&#xff08;&#xff09;&#xff1f; 如果没有&#xff0c;建议再给自己两巴掌。
阅读更多...
最新文章

Copyright @ 2022~2023