【数据结构】堆(Heap)

文章目录

  • 一、堆的概念及结构
  • 二、堆的实现
    • 1.向上调整算法
    • 2.向下调整算法
    • 3.堆的创建
    • 4.堆的插入
    • 5.堆的删除
    • 6.堆的其他操作
  • 三、堆的应用
    • 1.堆排序
    • 2.Top-K问题

一、堆的概念及结构

堆(Heap)是一种特殊的非线性结构。堆中的元素是按完全二叉树的顺序存储方式存储在数组 中。满足任意结点的值都大于等于左右子结点的值，叫做大堆，或者大根堆；反之，则是小堆，或者小根堆。

不熟悉二叉树的小伙伴可以先跳转→二叉树详解←学习。

堆分为小根堆和大根堆。

小根堆：所有父结点都小于等于左右孩子结点。
大根堆：所有父结点都大于等于左右孩子结点。

在这里插入图片描述

堆的性质：

1.堆是一棵完全二叉树。
2.堆中某个节点的值总是不大于或不小于其父节点的值。
3.如果一个堆为大（小）根堆，则它的左右子树也都是大（小）根堆。
4.小堆的存储结构不是升序，大堆的存储结构也不是降序。
5.堆中任意结点下标为 i，则它的左孩子结点下标为2i+1，右孩子结点下标为2i+2，父结点下标为(i-1)/2。

二、堆的实现

堆的两个重要算法：向上调整和向下调整。

1.向上调整算法

向上调整一般在堆中插入元素时使用。

具体实现(小根堆示例)：
1.给定一个数组和一个结点下标，该结点与其父结点的值进行比较。
2.如果该结点的值 ≥ 其父结点的值，已经是小堆了，则不再继续调整；
3.如果该结点的值 < 其父结点的值，需要将二者交换，然后将父结点当做孩子结点，继续向上对比和交换，直到调整到堆顶。

如果是小根堆，只需要改变判断符号>改为<即可。

//小根堆 向上调整
void AdjustUp(DataType* a, int child)
{
	int parent = (child - 1) / 2;//父结点下标
	while (a[child] < a[parent])//建大堆
	{
		Swap(&a[child], &a[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
}
//交换函数
void Swap(DataType* p1, DataType* p2)
{
	DataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

向上调整算法的比较次数最多不超过二叉树的高度，所以时间复杂度为O(logN)

2.向下调整算法

堆的向下调整算法比较常用，堆排序和堆的创建都会用到向下调整算法。

向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

具体实现(小根堆示例)：
1.从该结点开始，与其左右孩子结点中比较大（较小）的结点进行比较。
2.如果该结点的值 ≤ 其较小（较大）孩子结点的值，已经是小堆了，则不再继续调整；
3.如果该结点的值 > 其较小（较大）孩子结点的值，需要将二者交换，然后将较小的孩子结点当做父结点，继续向下对比和交换，直到调整到叶子结点。
在这里插入图片描述

//向下调整
void AdjustDown(DataType* a, int parent, int n)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		//选出较小的孩子
		if (child + 1 < n && a[child + 1] < a[child])//右孩子不能越界访问，注意判断顺序不能反
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

同样，向下调整算法的比较次数最多也不会超过二叉树的高度，所以时间复杂度为O(logN)

3.堆的创建

给定一个数组，怎么创建成一个堆呢？ 根结点的左右子树都不是堆，该怎么调整？

向上调整建堆：

从根结点开始调整

从根结点的左孩子结点开始（因为根结点本身可以看做一个堆），每个结点都向上调整，此时该结点前面的所有结点都已经构成了一个堆，直到调整到最后一个结点，就可以调整成堆。

// 向上调整建堆 效率O(N*logN)
for (int i = 1; i < n; i++)
{
    AdjustUp(a, i);
}

在这里插入图片描述向上调整建堆的时间复杂度是多少？

每个结点最多需要向上调整的次数与层数有关，若层数为k，则最多最多向上调整logk次。而随着层数越大，每层的结点数也越多。假设二叉树的高度为h，则向上调整为堆最多需要调整的次数为0×20+1×21+2×22+3×23+…+(h-1)×2h-1
= (h-2)×2h（错位相减，高中知识，具体过程略），又因为树的高度h=log(n+1)，所以时间复杂度的量级为O(N*logN)。

向下调整建堆：

从最后一个非叶子结点开始倒着调整

因为向下调整建堆需要满足左右子树都是堆的前提，所以我们可以从最后一个结点开始依次向下调整，因为最后一个结点本身可以看做是一个堆。但是因为叶子结点向下调整并不会发生变化，所以我们可以优化代码，从最后一个叶子结点的父结点也就是最后一个非叶子结点开始调整。

//向下调整建堆 效率O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
    AdjustDown(a, i, n);
}

在这里插入图片描述向下调整建堆的时间复杂度是多少？

因为向下调整建堆是从最后一个非叶子结点开始倒着调整的，随着层数的减小，每层的结点数也越少，但是结点向下调整的次数在增加，具体推导过程这里不过多介绍，最后的时间复杂度的量级是O(N)。


在这里插入图片描述

综上所述，向上调整建堆的时间复杂度为O(N*logN)，向下调整建堆的时间复杂度为O(N)，所以使用向下调整建堆的效率更高效。实际应用中，一般都使用向下调整算法建堆。

堆的定义、初始化、销毁
堆是以数组的方式存储的，所以堆的定义、初始化、销毁和顺序表一样。

#define INIT_SZ 10//初始空间大小
#define INC_SZ 4	//每次扩容的数量
typedef int HDataType;
typedef struct Heap
{
	HDataType* a;
	int size;
	int capacity;
}Heap;

//初始化
void HeapInit(Heap* php)
{
	assert(php);
	php->a = (HDataType*)malloc(sizeof(HDataType) * INIT_SZ);
	if (NULL == php->a)
	{
		perror("malloc");
		return;
	}
	php->size = 0;
	php->capacity = INIT_SZ;
}

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

4.堆的插入

堆的插入需要用到向上调整算法。

实现步骤：
1.在堆的末尾插入一个元素；
2.该元素向上调整，直到满足堆的性质。
在这里插入图片描述

//入堆
void HeapPush(Heap* php, HDataType x)
{
	assert(php);
	//扩容
	if (php->size == php->capacity)
	{
		HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * (INC_SZ + php->capacity));
		if (NULL == tmp)
		{
			perror("malloc");
			return;
		}
		php->a = tmp;
		php->capacity += INC_SZ;
	}
	php->a[php->size++] = x;//尾插
	AdjustUp(php->a, php->size - 1);//向上调整
}

5.堆的删除

删除的是堆顶的元素，删除之后仍然保证是堆
堆的删除需要用到向下调整算法。

实现步骤：
1.将堆顶元素与最后一个元素交换；
2.堆长度-1，即删除最后一个位置；
3.将交换后的堆顶元素向下调整。
在这里插入图片描述

void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	//将尾数据和堆顶数据交换，交换后的堆顶元素再向下调整
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;//堆的有效长度-1
	AdjustDown(php->a, 0, php->size);
}

6.堆的其他操作

//返回堆顶元素
HDataType HeapTop(Heap* php)
{
	assert(php);
	return php->a[0];
}
//判堆空
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}
//堆的元素个数
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}

三、堆的应用

1.堆排序

从前面的学习我们知道，堆结构的层序遍历，也就是从上到下每一层的从左到右，并非是有序的，也就是说堆存储在数组中的数据并不是有序的。比如下面这个大根堆，在数组中就是10,5,9,4,3,1,7 我们如何利用堆的特性将这些数据排序呢？
在这里插入图片描述
我们知道，大根堆的堆顶一定是最大的，小根堆的堆顶一定是最小的，所以利用这一个特点，我们可以取出堆顶元素，然后将剩下的元素重新调整成堆，再取堆顶元素，再调整剩下的元素，依次类推直到最后一个元素，就可以实现堆排序了。

但是，如果我们将堆顶元素按兵不动，将剩下的元素原地调整成堆，但剩下的元素会被完全打乱，完全不符合堆的性质，需要重新建堆，最后虽然也可以排序，但是效率却很低。这样的话跟普通排序没什么区别，每次找最大值（最小值）就好了，并没有用到堆的优势。

在这里插入图片描述

堆排序的实现步骤：
1.先将数组建堆；
2.将堆顶元素与堆末尾元素交换；
3.堆有效长度-1；
4.再将堆顶元素向下调整，直到调整到成堆

这不就是先建一个堆，再进行堆的删除操作吗？没毛病，原理是一样的。

比如一个大根堆，我们取出堆顶元素（最大数）与最后一个数交换，交换后的最大数不看作在堆里面，那么堆顶元素的左右子树仍满足堆的性质，堆的结构并没有被破坏，然后堆顶元素向下调整成堆，即可选出第二大的数，以此类推到最后一个元素，就可以成功实现堆排序了。

堆排序就是每次将堆顶元素从数组的末尾往前放，所以排升序建大堆，排降序建小堆

//堆排序
void HeapSort(int* a, int n)
{
    //建堆：排升序建大堆，排降序建小堆
    //倒着调整，从最后一个非叶子结点开始向下调整建堆 效率O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, i, n);
    }

    //O(N*logN)
    int end = n - 1;//堆的有效长度
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, 0, end);
        end--;
    }
}

堆排序的时间复杂度是O(N*logN)

2.Top-K问题

Top-K问题：求集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：游戏中排行榜前50名，全校前10名等。

对于Top-K问题，自然第一个想到的就是排序，没毛病。但是数据量很大的情况下，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。

第二种方法就是用堆来解决。

实现方法：

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

如果选前k个最大值，需要建小堆。
原理分析：小堆的堆顶元素是这k个数据中最小的元素，如果剩下N-K个元素中有大于堆中最小值的，说明这个数可以进入前k名；如果剩下N-K个元素中有小于堆中最小值的，则无法进入前k名。但是如果建大堆的话，堆顶元素就无法作为标准了。

void TopK(int* a, int n, int k)
{
    //用a中前k个元素建堆
    for (int i = (k - 2) / 2; i >= 0; i--)
        AdjustDown(a, i, k);
    for (int i = k; i < n; i++)
    {
        if (a[i] < a[0])
        {
            Swap(&a[i], &a[0]);//不满足则交换
            AdjustDown(a, 0, k);//向下调整
        }
    }
    for (int i = 0; i < k; i++)
        printf("%d ", a[i]);
}

上述代码只是选出前k个最大值或最小值，并没有将这k个数排序，如果要实现排序功能自行添加即可。

堆的完整代码放在gitee：https://gitee.com/ncu-ball/study/tree/master/24_4_19

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

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

相关文章

【送书福利第七期】你好！Java（文末送书）

【送书福利第七期】你好！Java（文末送书）

文章目录 编辑推荐内容简介作者简介目录前言/序言 编辑推荐 适读人群 &#xff1a;程序员;相关院校师生 本书以轻松幽默的语言&#xff0c;从零开始介绍Java语言。书名来源于编程语言中最经典的Hello World程序&#xff0c;寓意带读者从入门到精通。 书中每章都设有总结与扩展…
阅读更多...
开源软件托管平台gogs操作注意事项

开源软件托管平台gogs操作注意事项

文章目录 一、基本说明二、gogs私有化部署三、设置仓库git链接自动生成参数四、关闭新用户注册入口 私有化部署gogs托管平台&#xff0c;即把gogs安装在我们自己的电脑或者云服务器上。 一、基本说明 系统环境&#xff1a;ubuntu 20.4docker安装 二、gogs私有化部署 前期准…
阅读更多...
深入学习心理学才知道以前高估了自己的交易能力

深入学习心理学才知道以前高估了自己的交易能力

人的大脑总是能带来无限的惊喜。你能同时完成很多种工作而没有觉察你自己正在做这些事情。比如你一边开车一边打电话讨论着很严肃的事&#xff0c;边吃饭边用眼睛关心着后排坐着的孩子。除了这些外部的动作&#xff0c;你的内脏机能也在马不停蹄的工作着。这一切并不需要我们付…
阅读更多...
【Shell】正则表达式的操作实例

【Shell】正则表达式的操作实例

正则表达式是一个描述一组字符串的模式 是由普通字符和元字符组成的字符集&#xff0c;而这个字符集匹配&#xff08;或指定&#xff09;一个模式。 正则表达式的操作实例 &#xff08;一&#xff09;概述1.定义2.作用3.类型 &#xff08;二&#xff09;字符串匹配实例&#xf…
阅读更多...
掌握 Spring Boot 观察者模式：打造松耦合事件驱动应用程序

掌握 Spring Boot 观察者模式：打造松耦合事件驱动应用程序

掌握 Spring Boot 观察者模式&#xff1a;打造松耦合事件驱动应用程序 观察者模式是一种常用的设计模式&#xff0c;用于解决事件驱动编程中的问题。该模式定义了一对多的依赖关系&#xff0c;其中一个对象&#xff08;主题&#xff09;向一组依赖它的对象&#xff08;观察者&a…
阅读更多...
【phpstorm】根据等号对键值对进行自动对齐

【phpstorm】根据等号对键值对进行自动对齐

对于强迫症的我&#xff0c;看到这样的代码&#xff0c;总想给它整理一番。 可以通过 ide 配置&#xff0c;手动格式化代码&#xff0c;整理成这样&#xff1a; ide 版本&#xff1a; PhpStorm 2023.1.3 配置路径&#xff1a; Setting -> Editor -> Code Style -> PH…
阅读更多...
智能酒精壁炉与酒店前台的氛围搭配

智能酒精壁炉与酒店前台的氛围搭配

智能酒精壁炉与酒店前台的氛围搭配可以为前台区域增添舒适、现代和独特的氛围&#xff0c;以下是一些建议&#xff1a; 欢迎区域装饰&#xff1a; 将智能酒精壁炉作为前台欢迎区域的装饰物&#xff0c;放置在客人抵达的显眼位置。选择现代设计的壁炉款式&#xff0c;如壁挂式…
阅读更多...
SpringBoot整合SpringScurity权限控制（菜单权限，按钮权限）以及加上SSH实现安全传输

SpringBoot整合SpringScurity权限控制（菜单权限，按钮权限）以及加上SSH实现安全传输

文章目录 项目地址&#xff1a; 一、md5 与 先进的哈希算法的区别1.1. 安全性问题1.2. 设计目的1.3. 功能特性1.4. 适用性1.5. 总结 二、数据传输安全和数据加密实现&#xff1a;2.1 生成证书&#xff1a;2.2、在springboot中进行集成2.2.1 配置证书&#xff1a;2.2.2. 强制使用…
阅读更多...
Pytorch 与 Tensorflow：深度学习的主要区别（1）

Pytorch 与 Tensorflow：深度学习的主要区别（1）

引言 目前&#xff0c;Python 深度学习领域已经涌现出多个由科技界巨头如 Google、Facebook 和 Uber 等公司公开发布的框架&#xff0c;这些框架旨在帮助开发者构建先进的计算架构。对于刚接触这一领域的你来说&#xff0c;深度学习是计算机科学中的一个分支&#xff0c;它通过…
阅读更多...
springboot306基于Java的民宿管理系统（源码+包运行+配套LW+技术指导）

springboot306基于Java的民宿管理系统（源码+包运行+配套LW+技术指导）

项目描述 临近学期结束&#xff0c;开始毕业设计制作&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉的困难吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。今天给大家介绍一篇基于Java的民宿管理…
阅读更多...
初识指针（5）＜C语言＞

初识指针（5）＜C语言＞

前言 在前几篇文章中&#xff0c;已经介绍了指针一些基本概念、用途和一些不同类型的指针&#xff0c;下文将介绍某些指针类型的运用。本文主要介绍函数指针数组、转移表&#xff08;函数指针的用途&#xff09;、回调函数、qsort使用举例等。 函数指针数组 函数指针数组即每个…
阅读更多...
24年做抖音小店，你还停留在数据？别人都已经开始注重利润了

24年做抖音小店，你还停留在数据？别人都已经开始注重利润了

大家好&#xff0c;我是电商笨笨熊 一件事情持续做&#xff0c;一个项目持续深耕&#xff0c;意义到底是什么&#xff1f; 这句话我常常说&#xff0c;但很多人似乎走偏了实际意义&#xff1b; 尤其对于新手来说&#xff0c;做抖音小店总是向往某某老玩家多么牛的数据&#…
阅读更多...
如何把握人力RPO的蓝海机遇？实战策略分享！

如何把握人力RPO的蓝海机遇？实战策略分享！

随着企业间竞争的日益激烈&#xff0c;人力资源管理的重要性愈发凸显。在众多人力资源管理策略中&#xff0c;招聘流程外包(RPO)作为一种新兴的服务模式&#xff0c;逐渐受到业界的关注。那么&#xff0c;人力RPO是否是蓝海项目?我们又该如何实施RPO呢? 一、人力RPO&#xff…
阅读更多...
C++干货--引用

C++干货--引用

前言&#xff1a; C的引用&#xff0c;是学习C的重点之一&#xff0c;它与指针的作用有重叠的部分&#xff0c;但是它绝不是完全取代指针(后面我们也会简单的分析)。 引用的概念&#xff1a; 引用 不是新定义一个变量 &#xff0c;而 是给已存在变量取了一个别名 &#xf…
阅读更多...
经典文献阅读之--D-Map(无需射线投射的高分辨率激光雷达传感器的占据栅格地图)

经典文献阅读之--D-Map(无需射线投射的高分辨率激光雷达传感器的占据栅格地图)

0. 简介 占用地图是机器人系统中推理环境未知和已知区域的基本组成部分。《Occupancy Grid Mapping without Ray-Casting for High-resolution LiDAR Sensors》介绍了一种高分辨率LiDAR传感器的高效占用地图框架&#xff0c;称为D-Map。该框架引入了三个主要创新来解决占用地图…
阅读更多...
附录2 创建flask镜像

附录2 创建flask镜像

目录 1 python镜像 2 安装flask 3 把项目文件扔进去 3.1 创建git仓库 3.2 上传文件 3.3 获取git链接 3.4 在容器中git clone 4 启动flask服务 5 将容器保存为镜像 6 映射端口运行镜像 7 遇到的问题 8 Dockerfile创建镜像 1 python镜像 首先找一下fla…
阅读更多...
Android 老年模式功能 放大字体

Android 老年模式功能 放大字体

1 配置属性 <attr name"text_size_16" format"dimension"/><attr name"text_size_18" format"dimension"/><attr name"text_size_14" format"dimension"/><attr name"text_size_12&quo…
阅读更多...
MySQL中的索引失效问题

MySQL中的索引失效问题

索引失效的情况 这是正常查询情况&#xff0c;满足最左前缀&#xff0c;先查有先度高的索引。 1. 注意这里最后一种情况&#xff0c;这里和上面只查询 name 小米科技 的命中情况一样。说明索引部分丢失&#xff01; 2. 这里第二条sql中的&#xff0c;status > 1 就是范围查…
阅读更多...
咸鱼之王游戏攻略：平民怎么起号？

咸鱼之王游戏攻略：平民怎么起号？

在《咸鱼之王》这款游戏中&#xff0c;即使是平民玩家&#xff0c;也有着许多可以优化的操作&#xff0c;以最大程度地提高收益。本攻略将针对平民玩家的日常操作进行详细解读&#xff0c;包括黑市购买、资源管理等方面的建议&#xff0c;希望对广大玩家有所帮助。 一、黑市购买…
阅读更多...
Vue的学习 —— ＜vue的开发环境＞ “6000字超详细”

Vue的学习 —— ＜vue的开发环境＞ “6000字超详细”

目录 前言 学习目标 正篇开始 —— 部署vue开发环境 一、Visual Studio Code编辑器 1、简介 2、下载和安装VSCode编辑器 3、安装中文插件 4、安装Volar插件 5、使用VCode编辑器 二、Node.js环境 简介 下载和安装Node.js环境 三、包管理工具 1、简介 2、配置npm …
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站