当前位置: 首页 > news >正文

堆以及堆的实现

文章目录

  • 堆的概念
  • 堆的实现
    • HeapPush
    • HeapPop
  • HeapTop HeapSize HeapEmpty
  • 堆的应用

堆的概念

  • 堆是一颗完全二叉树
  • 每个结点的值都小于子结点的值,这颗二叉树为小根堆
  • 每个结点的值都大于子结点的值,这颗二叉树为大根堆
  • 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    在这里插入图片描述
    堆的性质
  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

堆的实现

在讲堆的实现前,我们首先要知道堆需要实现的功能。

  • HeapPush
  • HeapPop(删除根结点)
  • HeapTop
  • HeapSize
  • HeapEmpty
    接下来我们要先创建和销毁一个堆。
typedef int HeapType;
typedef struct Heap
{HeapType* arr;int size;int capacity;
}Hp;
void HeapInit(Hp* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}
void HeapDestroy(Hp* php)
{assert(php);free(php->arr);php->arr = NULL;php->capacity = php->size = 0;
}

HeapPush

实现HeapPush时难点在于如何保持整体是一个堆。
即在一个堆的后面插入一个值,那么这棵完全二叉树大概率不会是堆,那么我们需要将这个值和其父结点比较,再根据需要交换值,也就是AdjustUp。
那么接下来以小根堆为例,实现HeapPush。

void Swap(HeapType* a, HeapType* b)
{HeapType tmp = *a;*a = *b;*b = tmp;
}
void AdjustUp(HeapType* arr, int child)
{int 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 HeapPush(Hp* php, HeapType x)
{assert(php);if (php->size == php->capacity){int newcapacity = (php->capacity == 0 ? 4 : 2 * php->capacity);HeapType * tmp = (HeapType*)realloc(php->arr,newcapacity * sizeof(HeapType));if (!tmp){perror("realloc fail!");exit(-1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;php->size++;AdjustUp(php->arr, php->size - 1);
}

HeapPop

实现HeapPop也是和HeapPush一样,需要考虑的是如何维持整体完全二叉树是一个堆,由于我们删除的是根结点,如果将根结点的子结点向上调整,那么整体二叉树就会空出一个位置,导致变成非完全二叉树。
这里的解决办法是将根结点和最后一个结点交换,删除最后一个结点,然后再对根结点进行向下调整。

void AdjustDown(HeapType* a, int n, int parent)
{int child = 2 * parent + 1;while (child<n){if (child + 1 < n && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent - 1;}else{break;}}
}
void HeapPop(Hp* php)
{assert(php);assert(php->size);Swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;AdjustDown(php->arr, php->size, 0);
}

HeapTop HeapSize HeapEmpty

实现了Heap的Push和Pop后,那么取根结点的值和判空、判满也是手到擒来的。

HeapType HeapTop(Hp* php)
{assert(php);assert(php->size);return php->arr[0];
}
size_t HeapSize(Hp* php)
{assert(php);return php->size;
}
bool HeapEmpty(Hp* php)
{assert(php);return php->size == 0;
}

堆的应用

实现了堆那么我们肯定要知道能用在什么地方才行,实际上堆的应用也是非常广泛的:

  1. 实现堆排序
  2. 求Top K值问题
  3. 求中位数、百分位数

等等。
堆的应用还有很多,这里就不一一赘述了。

相关文章:

堆以及堆的实现

文章目录 堆的概念堆的实现HeapPushHeapPop HeapTop HeapSize HeapEmpty堆的应用 堆的概念 堆是一颗完全二叉树每个结点的值都小于子结点的值&#xff0c;这颗二叉树为小根堆每个结点的值都大于子结点的值&#xff0c;这颗二叉树为大根堆堆的定义如下&#xff1a;n个元素的序列…...

使用RabbitMQ实现延时消息自动取消的简单案例

一、流程图 二、导包 <!--消息队列 AMQP依赖&#xff0c;包含RabbitMQ--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </dependency> 三、配置文件 #消息队列 …...

Docker部署(ruoyi案例接上篇Docker之部署前后端分离项目)实施必会!!!!

文章目录 Docker部署前端 Docker部署前端 接上篇博主已经部署好后端Docker部署后端&#xff0c;现在来讲解怎么部署前端 MySQL和redis是不依赖其他任何一个东西的&#xff0c; ruoyi-admin是因为你启动项目的时候是必须连接数据库的 现在去单独启动它 docker start ruoyi-a…...

电脑中已经有多个模组压缩文件,如何通过小火星露谷管理器批量安装

如果已经下载了很多的星露谷模组压缩文件&#xff08;zip包&#xff09;&#xff0c;可以通过【添加模组】功能&#xff0c;将模组批量解压到Mods文件夹中。 名词解释 为了避免这篇文章的内容看不懂&#xff0c;先解释两个名词。 直装型模组&#xff1a;直接解压到Mods就能生…...

[Linux]如何理解kernel、shell、bash

文章目录 概念总览kernelshell&bash 概念总览 内核(kernel) &#xff0c;外壳(shell) &#xff0c;bash kernel kernel是指操作系统中的核心部分&#xff0c;用户一般是不能直接使用kernel的。它主要负责管理硬件资源和提供系统服务&#xff0c;如内存管理、进程管理、文件…...

C++:Vector的使用

一、vector的介绍 vector的文档介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可以…...

Redis之事务(详细解析)

请直接看原文:不能回滚的Redis事务还能用吗 - 知乎 (zhihu.com) ------------------------------------------------------------------------------------------------------------------------------ 1、Redis事务的概念&#xff1a; Redis 事务的本质是一组命令的集合。…...

Java项目:39 springboot007大学生租房平台的设计与实现

作者主页&#xff1a;源码空间codegym 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 系统有管理员、房东和用户 【主要功能】 1、后台&#xff1a;房源管理、信息审批管理、订单信息管理、房东管理、用户管理 2、前台&#xff1…...

安卓内存信息查看

目录 前言一、Android查看内存相关信息的方法1.1 通过 adb shell 获取内存信息1.2 通过编程方式获取内存信息1.3 adb shell 获取应用程序内存使用情况1.4 free指令 二、总结 前言 一、Android查看内存相关信息的方法 1.1 通过 adb shell 获取内存信息 C:\Users\henry.xue>…...

Positional Encoding 位置编码

Positional Encoding 位置编码 flyfish Transformer模型没有使用循环神经网络&#xff0c;无法从序列中学习到位置信息&#xff0c;并且它是并行结构&#xff0c;不是按位置来处理序列的&#xff0c;所以为输入序列加入了位置编码&#xff0c;将每个词的位置加入到了词向量中…...

MySql、Navicat 软件安装 + Navicat简单操作(建数据库,表)

一、MySql、Navicat 软件安装 及正常使用 MySql下载&#xff0b;安装&#xff1a; 检查安装情况&#xff1a; 配置环境变量&#xff1a; 搞定了&#xff01;&#xff01;&#xff01; 可以登陆试哈哈哈 连接navicat 开始创建数据库 二、 商品种类表 - commoditytype int …...

逆向案例五、爬取b站评论,表单MD5加密

1.便捷写爬虫网站&#xff1a; Convert curl commands to code 使用流程&#xff1a;又点击想要抓的包&#xff0c;复制URL&#xff08;base&#xff09;格式复制 在上面链接中粘贴即可 2.找到含有评论的包&#xff08;即main?oid)&#xff1a;观察表单发现两处参数在变化&…...

010-原型链

原型链 1、概念2、原理3、new 操作符原理4、应用 1、概念 原型链&#xff1a;javascript的继承机制&#xff0c;是指获取JavaScript对象的属性会顺着其_proto_的指向寻找&#xff0c;直至找到Object.prototype上。 2、原理 &#x1f4a1; Tips&#xff1a;构造函数 Fn&#…...

Electron-builder打包安装包——编译篇

突然有一天想打包个桌面程序&#xff0c;没有打包过&#xff0c;经过九牛二虎之力终于打包出来&#xff0c;在此感谢那些热于分享的前辈&#xff01; 本篇只讲打包运行和出现的问题 一、准备工作&#xff1a;提前下载相关资源包&#xff0c;否则在国内环境下可能因为网络问题…...

Red Hat系统升级内核版本

查看当前内核版本 uneme -r yum list kernel升级内核 yum update -y kernel检查升级后的内核版本 uneme -r yum list kernel升级系统中已安装的软件包到最新版本&#xff08;过程时间较长&#xff09; 目前只升级了系统内核&#xff0c;系统相关的安装包还是老的&#xff0…...

Java集合set之HashSet、LinkedHashSet、TreeSet的区别?

Java的集合中主要由List&#xff0c;Set&#xff0c;Queue&#xff0c;Map构成&#xff0c;Set特点&#xff1a;存取无序&#xff0c;不可以存放重复的元素&#xff0c;不可以用下标对元素进行操作。 HashSet 作为Set容器的代表子类&#xff0c;HashSet经常被用到&#xff0c…...

全方位碾压chatGPT4的全球最强模型Claude 3发布!速通指南在此!保姆级教学拿脚都能学会!

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…...

upload-Labs靶场“11-15”关通关教程

君衍. 一、第十一关 %00截断GET上传1、源码分析2、%00截断GET上传 二、第十二关 %00截断POST上传1、源码分析2、%00截断POST上传 三、第十三关 文件头检测绕过1、源码分析2、文件头检测绕过 四、第十四关 图片检测绕过上传1、源码分析2、图片马绕过上传 五、第十五关 图片检测绕…...

linux-rpm命令

rpm命令管理程序包&#xff1a;安装、升级、卸载、查询和校验 1、忽略依赖关系安装/卸载包 安装&#xff1a;rpm -Uvh 软件包名 --nodeps 卸载&#xff1a;rpm -e 软件包名 --nodes&#xff01;&#xff01;&#xff01;&#xff01;慎用&#xff01;&#xff01;&#xff01…...

如何利用python实现自己的modbus-tcp库

如果你想使用纯Socket编程来实现Modbus TCP通讯,而不是依赖于Modbus库,你需要理解Modbus TCP协议的细节,并能够手动构建和解析Modbus消息。以下是一个简单的示例,展示了如何使用Python的socket库来实现Modbus TCP通讯: 了解Modbus TCP协议: Modbus TCP协议使用TCP作为底层…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...