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

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

PydanticAI快速入门示例

参考链接&#xff1a;https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...

学习 Hooks【Plan - June - Week 2】

一、React API React 提供了丰富的核心 API&#xff0c;用于创建组件、管理状态、处理副作用、优化性能等。本文档总结 React 常用的 API 方法和组件。 1. React 核心 API React.createElement(type, props, …children) 用于创建 React 元素&#xff0c;JSX 会被编译成该函数…...