数据结构:堆的实现
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 ,k2 ,k3 ,…,kn },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并且 k(i) < k(i*21) 和 k(i) < k(i*22), i 0 ÿ…...
zabbix-6.4 监控 MySQL
目录 1、rpm安装zabbix_agentd服务 2、编写zabbix_agentd.conf文件 3、编写模板文件 4、创建mysql用户并赋权限 5、创建.my.cnf文件 6、将规则添加到SELinux策略中 注意: 若模板无法读取.my.cnf 信息,从而导致监控报错,可以尝试修改模…...
深入探索:解读创意的力量——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创建一个新的项目(模块&am…...
Redis详解
Redis 简介 Redis(Remote Dictionary Server)是一个开源的高性能键值对存储数据库,最初由 Salvatore Sanfilippo 开发,它在内存中存储数据,并提供了持久化功能,可以将数据保存到磁盘中,是一种N…...
【Linux】高级IO
目录 IO的基本概念 钓鱼五人组 五种IO模型 高级IO重要概念 同步通信 VS 异步通信 阻塞 VS 非阻塞 其他高级IO 阻塞IO 非阻塞IO IO的基本概念 什么是IO? I/O(input/output)也就是输入和输出,在著名的冯诺依曼体系结构当中…...
动态HTTP代理与竞争情报收集的关联
Hey,各位爬友们!作为一名专业的爬虫HTTP代理提供者,今天我要和大家聊一聊动态HTTP代理与竞争情报收集之间的关联。在这篇文章中,我将向大家解释怎么使用动态HTTP代理完成在竞争中的情报收集,并分享一些实用的技巧。 首…...
kafka基本概念及操作
kafka介绍 Kafka是最初由Linkedin公司开发,是一个分布式、支持分区的(partition)、多副本的 (replica),基于zookeeper协调的分布式消息系统,它的最大的特性就是可以实时的处理大量数据以满足各…...
分享个试卷去笔迹什么软件,几个步骤轻松擦除
试卷擦去笔迹是一项非常关键的技能,它可以帮助你更好地管理你的笔记和文件。不管是小伙伴们想重新测试试卷或者是将试卷输出为电子版,都可以实现的。在这篇文章中,我将分享一些方法和软件,帮助你更好地进行试卷擦除。有需要的小伙…...
ClickHouse(十八):Clickhouse Integration系列表引擎
进入正文前,感谢宝子们订阅专题、点赞、评论、收藏!关注IT贫道,获取高质量博客内容! 🏡个人主页:含各种IT体系技术,IT贫道_Apache Doris,大数据OLAP体系技术栈,Kerberos安全认证-CSDN博客 &…...
日常BUG——代码提交到了本地但是没有push,删除了本地分支如何恢复
😜作 者:是江迪呀✒️本文关键词:日常BUG、BUG、问题分析☀️每日 一言 :存在错误说明你在进步! 一、问题描述 代码在本地提交了,但是没有push到远程,然后删除了本地的分支。想要恢…...
Markdown语法
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 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 报错:报表服务器无法访问服务帐户的私钥
解决这个问题,有小伙伴提到可以使用命令 exec DeleteEncryptedContent 但这对这边的环境时行不通的,我在【服务账户】的配置和【数据库】的配置中到使用了域账户,试了几次都不行。改成使用内置账户就好了。具体原因还没扒拉(欢迎…...
QT报表Limereport v1.5.35编译及使用
1、编译说明 下载后QT CREATER中打开limereport.pro然后直接编译就可以了。编译后结果如下图: 一次编译可以得到库文件和DEMO执行程序。 2、使用说明 拷贝如下图编译后的lib目录到自己的工程目录中。 release版本的重新命名为librelease. PRO文件中配置 QT …...
互联网发展历程:从中继器口不够到集线器的引入
互联网的发展,就像一场不断演进的技术盛宴,每一步的变革都在推动着我们的世界向前。然而,在网络的早期,一项重要的技术问题曾困扰着人们:当中继器的接口数量不足时,如何连接更多的设备?这时&…...
vue+flask基于知识图谱的抑郁症问答系统
vueflask基于知识图谱的抑郁症问答系统 抑郁症已经成为当今社会刻不容缓需要解决的问题,抑郁症的危害主要有以下几种:1.可导致病人情绪低落:抑郁症的病人长期处于悲观的状态中,感觉不到快乐,总是高兴不起来。2.可导致工…...
操作格子---算法集
问题描述 有 n 个格子,从左到右放成一排,编号为 1-n。 共有 m 次操作,有 3 种操作类型: 1.修改一个格子的权值。 2.求连续一段格子权值和。 3.求连续一段格子的最大值。 对于每个 2、3 操作输出你所求出的结果。 输入格式 第一行 …...
科研绘图chapter1:绘图原则与配色基础
本系列会持续更新,主要参考datawhale的开源课程。详见: 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,这里记录一下ossrs支持的WebRTC本地服务搭建。 一、ossrs是什么? ossrs是什么呢? SRS(Simple Realtime Server)是一个简单高效的实时视频服务器,支持RTM…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
