当前位置: 首页 > 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作为底层…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...