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

数据结构:堆的实现

1.堆的概念

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

1.1堆的性质 

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

1.2堆的存储结构

 

2.堆的实现

  堆的构建
 堆的销毁
 堆的插入
  堆的删除
  取堆顶的数据
  堆的数据个数
  堆的判空

2.1堆的构造与销毁

 

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

 2.2堆的向上与向下调整

void swap(DataType*str1, DataType*str2)
{DataType temp = *str1;*str1 = *str2;*str2 = temp;
}
//向上调整(前提是上面是一个堆)
void AdjustUp(DataType* a, int child)
{//利用孩子找父亲,并且比较int parent = (child - 1) / 2;while (child > 0){// "<" 和 ">"取决与建立大小堆if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//向下调整(前提是下面左右子树是一个堆)
void AdjustDown(int* a, int n, int parent)//n是数量
{//利用父亲找儿子并比较大小int child = parent * 2 + 1;while (child < n){//child + 1 < n可能没有右孩子,防止越界风险if (child + 1 < n && a[child + 1] < a[child]){child++;}// "<" 和 ">"取决与建立大小堆if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;int child = parent * 2 + 1;}elsebreak;}
}

2.3 堆的插入与堆的删除

//先插入一个数到数组的尾上,再进行向上调整算法,直到满足堆
void HeapPush(HP* php, DataType x)
{assert(php);//判断是否要扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;DataType* temp = (DataType*)realloc(php->a, newCapacity * sizeof(DataType));if (temp == NULL){perror("realloc fail");return;}php->a = temp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
//删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组
//最后一个数据,再进行向下调整算法。
void HeapPop(HP* php)
{assert(php);swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

2.4堆的数据个数与堆的判空和取得堆的堆顶元素

DataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}

相关文章:

数据结构:堆的实现

1.堆的概念 如果有一个关键码的集合 K { k1 &#xff0c;k2 &#xff0c;k3 &#xff0c;…&#xff0c;kn }&#xff0c;把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中&#xff0c;并且 k(i) < k(i*21) 和 k(i) < k(i*22)&#xff0c; i 0 &#xff…...

zabbix-6.4 监控 MySQL

目录 1、rpm安装zabbix_agentd服务 2、编写zabbix_agentd.conf文件 3、编写模板文件 4、创建mysql用户并赋权限 5、创建.my.cnf文件 6、将规则添加到SELinux策略中 注意&#xff1a; 若模板无法读取.my.cnf 信息&#xff0c;从而导致监控报错&#xff0c;可以尝试修改模…...

深入探索:解读创意的力量——idea的下载、初步使用

目录 ​编辑 1.IDEA的简介 2.IDEA的下载 2.1下载路径https://www.jetbrains.com/zh-cn/idea/download/?sectionwindows​编辑​ 2.2下载的步骤 3 idea的初步使用 3.1新建一个简单的Java项目 3.1.1首先需要创建一个新的工程 3.1.2创建一个新的项目&#xff08;模块&am…...

Redis详解

Redis 简介 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的高性能键值对存储数据库&#xff0c;最初由 Salvatore Sanfilippo 开发&#xff0c;它在内存中存储数据&#xff0c;并提供了持久化功能&#xff0c;可以将数据保存到磁盘中&#xff0c;是一种N…...

【Linux】高级IO

目录 IO的基本概念 钓鱼五人组 五种IO模型 高级IO重要概念 同步通信 VS 异步通信 阻塞 VS 非阻塞 其他高级IO 阻塞IO 非阻塞IO IO的基本概念 什么是IO&#xff1f; I/O&#xff08;input/output&#xff09;也就是输入和输出&#xff0c;在著名的冯诺依曼体系结构当中…...

动态HTTP代理与竞争情报收集的关联

Hey&#xff0c;各位爬友们&#xff01;作为一名专业的爬虫HTTP代理提供者&#xff0c;今天我要和大家聊一聊动态HTTP代理与竞争情报收集之间的关联。在这篇文章中&#xff0c;我将向大家解释怎么使用动态HTTP代理完成在竞争中的情报收集&#xff0c;并分享一些实用的技巧。 首…...

kafka基本概念及操作

kafka介绍 Kafka是最初由Linkedin公司开发&#xff0c;是一个分布式、支持分区的&#xff08;partition&#xff09;、多副本的 &#xff08;replica&#xff09;&#xff0c;基于zookeeper协调的分布式消息系统&#xff0c;它的最大的特性就是可以实时的处理大量数据以满足各…...

分享个试卷去笔迹什么软件,几个步骤轻松擦除

试卷擦去笔迹是一项非常关键的技能&#xff0c;它可以帮助你更好地管理你的笔记和文件。不管是小伙伴们想重新测试试卷或者是将试卷输出为电子版&#xff0c;都可以实现的。在这篇文章中&#xff0c;我将分享一些方法和软件&#xff0c;帮助你更好地进行试卷擦除。有需要的小伙…...

ClickHouse(十八):Clickhouse Integration系列表引擎

进入正文前&#xff0c;感谢宝子们订阅专题、点赞、评论、收藏&#xff01;关注IT贫道&#xff0c;获取高质量博客内容&#xff01; &#x1f3e1;个人主页&#xff1a;含各种IT体系技术&#xff0c;IT贫道_Apache Doris,大数据OLAP体系技术栈,Kerberos安全认证-CSDN博客 &…...

日常BUG——代码提交到了本地但是没有push,删除了本地分支如何恢复

&#x1f61c;作 者&#xff1a;是江迪呀✒️本文关键词&#xff1a;日常BUG、BUG、问题分析☀️每日 一言 &#xff1a;存在错误说明你在进步&#xff01; 一、问题描述 代码在本地提交了&#xff0c;但是没有push到远程&#xff0c;然后删除了本地的分支。想要恢…...

Markdown语法

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 Markdown语法目录 前言1.标题2.文本样式3.列表四.图片5.链接6.目录7.代码片7.表格8.注脚9.注释10.自定义列表11.LaTeX数学公式12.插入甘特图13.插入UML图14.插入Merimaid流程…...

vue3表格,编辑案例

index.vue <script setup> import { onMounted, ref } from "vue"; import Edit from "./components/Edit.vue"; import axios from "axios";// TODO: 列表渲染 const list ref([]); const getList async () > {const res await ax…...

SQL Server Reporting Services 报错:报表服务器无法访问服务帐户的私钥

解决这个问题&#xff0c;有小伙伴提到可以使用命令 exec DeleteEncryptedContent 但这对这边的环境时行不通的&#xff0c;我在【服务账户】的配置和【数据库】的配置中到使用了域账户&#xff0c;试了几次都不行。改成使用内置账户就好了。具体原因还没扒拉&#xff08;欢迎…...

QT报表Limereport v1.5.35编译及使用

1、编译说明 下载后QT CREATER中打开limereport.pro然后直接编译就可以了。编译后结果如下图&#xff1a; 一次编译可以得到库文件和DEMO执行程序。 2、使用说明 拷贝如下图编译后的lib目录到自己的工程目录中。 release版本的重新命名为librelease. PRO文件中配置 QT …...

互联网发展历程:从中继器口不够到集线器的引入

互联网的发展&#xff0c;就像一场不断演进的技术盛宴&#xff0c;每一步的变革都在推动着我们的世界向前。然而&#xff0c;在网络的早期&#xff0c;一项重要的技术问题曾困扰着人们&#xff1a;当中继器的接口数量不足时&#xff0c;如何连接更多的设备&#xff1f;这时&…...

vue+flask基于知识图谱的抑郁症问答系统

vueflask基于知识图谱的抑郁症问答系统 抑郁症已经成为当今社会刻不容缓需要解决的问题&#xff0c;抑郁症的危害主要有以下几种&#xff1a;1.可导致病人情绪低落&#xff1a;抑郁症的病人长期处于悲观的状态中&#xff0c;感觉不到快乐&#xff0c;总是高兴不起来。2.可导致工…...

操作格子---算法集

问题描述 有 n 个格子&#xff0c;从左到右放成一排&#xff0c;编号为 1-n。 共有 m 次操作&#xff0c;有 3 种操作类型&#xff1a; 1.修改一个格子的权值。 2.求连续一段格子权值和。 3.求连续一段格子的最大值。 对于每个 2、3 操作输出你所求出的结果。 输入格式 第一行 …...

科研绘图chapter1:绘图原则与配色基础

本系列会持续更新&#xff0c;主要参考datawhale的开源课程。详见&#xff1a; https://github.com/datawhalechina/paper-chart-tutorial 文章目录 1.1 科研论文配图的绘制基础1.2 科研论文配图的配色基础1.2.1 配色模式1.2.2 色环配色原则1.3 配色工具/网站 1.1 科研论文配图…...

Linux下grep通配容易混淆的地方

先上一张图: 我希望找到某个版本为8的一个libXXX.8XXX.so ,那么应该怎么写呢? 先看这种写法对不对: 是不是结果出乎你的意料之外? 那么我们来看一下规则: 这里的 "*" 表示匹配前一个字符的零个或多个 于是我们就不难理解了: lib*8*.so 表示 包…...

WebRTC音视频通话-WebRTC本地视频通话使用ossrs服务搭建

iOS开发-ossrs服务WebRTC本地视频通话服务搭建 之前开发中使用到了ossrs&#xff0c;这里记录一下ossrs支持的WebRTC本地服务搭建。 一、ossrs是什么&#xff1f; ossrs是什么呢&#xff1f; SRS(Simple Realtime Server)是一个简单高效的实时视频服务器&#xff0c;支持RTM…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

初级程序员入门指南

初级程序员入门指南 在数字化浪潮中&#xff0c;编程已然成为极具价值的技能。对于渴望踏入程序员行列的新手而言&#xff0c;明晰入门路径与必备知识是开启征程的关键。本文将为初级程序员提供全面的入门指引。 一、明确学习方向 &#xff08;一&#xff09;编程语言抉择 编…...