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

[数据结构]堆

堆,本质是一颗完全二叉树。属于非线性结构。

代码实现可参考树的代码。

函数介绍:

//此堆是小堆,大堆操作部分与小堆相反
void InitHeap(Heap* cat)
{assert(cat);cat->arr = NULL;cat->capacity = cat->size = 0;
}
void DestroyHeap(Heap* cat)
{assert(cat);if (cat->arr)free(cat->arr);cat->arr = NULL;
}
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustUp(Type* 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(Heap* cat, Type x)
{assert(cat);if (cat->capacity == cat->size){int newcapacity = cat->capacity == 0 ? 4 : 2 * cat->capacity;Type* tmp = (Type*)realloc(cat->arr, newcapacity * sizeof(Type));if (tmp == NULL){perror("realloc fail!");exit(1);}cat->capacity = newcapacity;cat->arr = tmp;}cat->arr[cat->size++] = x;AdjutUp(cat->arr, cat->size);
}
void AdjustDown(Type* arr, int parent, int n)//小堆
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child] > arr[child + 1])//找{child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapPop(Heap* cat)
{assert(cat);Swap(&cat->arr[0], &cat->arr[cat->size - 1]);--cat->size;AdjustDown(cat->arr, 0, cat->size - 1);
}
//判空
bool HeapEmpty(Heap* cat)
{assert(cat);return cat->size == 0;
}
//输出堆顶数据
Type HeapTop(Heap* cat)
{assert(cat);return cat->arr[0];
}
//打印堆可用三种遍历方式打印或者树的层序遍历,此处省略

头文件介绍:

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int Type;
typedef struct Heap {Type* arr;int capacity;int size;
}Heap;
void InitHeap(Heap* cat);
void DestroyHeap(Heap* cat);
void Swap(int* x, int* y);
void AdjustUp(Type* arr, int child);
void HeapPush(Heap* cat, Type x);
void AdjustDown(Type* arr, int parent, int n);
void HeapPop(Heap* cat);
bool HeapEmpty(Heap* cat);
Type HeapTop(Heap* cat);

谢谢观看!

相关文章:

[数据结构]堆

堆&#xff0c;本质是一颗完全二叉树。属于非线性结构。 代码实现可参考树的代码。 函数介绍: //此堆是小堆,大堆操作部分与小堆相反 void InitHeap(Heap* cat) {assert(cat);cat->arr NULL;cat->capacity cat->size 0; } void DestroyHeap(Heap* cat) {assert(…...

UDP-鼠李糖合成酶基因的克隆与鉴定-文献精读76

何首乌中UDP-鼠李糖合成酶基因FmRHM1/2的克隆与鉴定 摘要 UDP-鼠李糖是一种由UDP-鼠李糖合酶&#xff08;RHM&#xff09;催化合成的鼠李糖供体&#xff0c;而鼠李糖是鼠李糖苷化合物的重要组成部分&#xff0c;植物中只有少数基因编码的酶参与UDP-鼠李糖生物合成。本研究基于…...

【H2O2|全栈】JS进阶知识(四)Ajax

目录 前言 开篇语 准备工作 基本概念 原生JS使用AJAX 创建AJAX对象 设置请求方式和地址 设置请求头 发送请求 get方式发送 post方式发送 获取响应数据 AJAX状态码和HTTP状态消息 错误捕获 原生JS封装AJAX方法 $ 调用AJAX方法 结束语 前言 开篇语 本系列博客…...

Spring IOC的工作流程

Spring IOC的工作流程 好的&#xff0c;这个问题我会从几个方面来回答。 IOC是什么 Bean的声明方式 IOC的工作流程 IOC的全称是 Inversion Of Control,也就是控制反转&#xff0c;它的核心思想是把对象的管理权限交给容器。&#xff08;展示图 1&#xff09; &…...

从新手到专家:7款电脑平面设计软件评测

平面设计在时尚、广告等多个领域扮演着重要角色&#xff0c;而创作出独特且富有创意的设计作品则需要依赖优秀的电脑平面设计软件。市场上的电脑平面设计软件众多&#xff0c;每款软件都有其独到之处。本文将为你推荐几款值得关注的电脑平面设计软件&#xff0c;并分析它们的特…...

【C++】如何让C++字符串更快、C++的小字符串优化

二十三、如何让C字符串更快、C的小字符串优化 1、如何让C字符串更快&#xff1f; 如果程序中有很多字符串操作&#xff0c;比如格式化文本(日志记录)&#xff0c;那是非常糟糕的&#xff0c;因为字符串操作是很慢的。字符串string和它相关的很多函数很可能会自动分配内存&…...

C++《list》

在本篇当中我们将学习STL中的list&#xff0c;在此list就是我们之前在数据结构学习过的链表&#xff0c;在本篇中我们要来了解list当中的成员函数该如何使用&#xff0c;由于list各个函数的接口和之前学习过的vector类型&#xff0c;因此在学习list的使用就较为轻松。在lis篇章…...

strongswan中METHOD定义

strongswan中使用METHOD来定义函数&#xff08;方法&#xff09;&#xff0c;如下get_first函数定义。 METHOD(linked_list_t, get_first, status_t,private_linked_list_t *this, void **item) {if (this->count 0)return NOT_FOUND;*item this->first->value;ret…...

Rive 动画框架竟然支持响应式布局,全平台动画框架开启全新 UI 交互能力

没用过 Rive 的可能对于 Rive 还不熟悉&#xff0c;其实之前已经介绍过 Rive 好几次&#xff0c;例如《Rive 2 动画库「完全商业化」》 和《给掘金 Logo 快速添加动画效果》 等文章都介绍过 Rive &#xff0c;之所以会接触 Rive 到&#xff0c; 也是因为多年前想在 Flutter 平台…...

MQ的详细大全知识点

MQ&#xff08;Message Queue&#xff09;是一种在分布式系统中广泛应用的消息中间件&#xff0c;它基于“先进先出”的数据结构原理&#xff0c;用于在不同系统之间传递消息。MQ通过提供接口给各个系统调用&#xff0c;实现了发送者和接收者之间的解耦&#xff0c;使得系统之间…...

AI图像相似性搜索对比:VIT, CLIP, DINO-v2, BLIP-2

图像相似性搜索的核心在于一个简单的想法&#xff1a;图像可以表示为高维空间中的向量。当两个图像相似时&#xff0c;它们的向量应该在这个空间中占据相似的位置。我们可以通过测量角度&#xff08;或余弦相似度&#xff09;来确定这些向量的相似程度。如果角度小&#xff0c;…...

【tomcat系列漏洞利用】

Tomcat 服务器是一个开源的轻量级Web应用服务器&#xff0c;在中小型系统和并发量小的场合下被普遍使用。主要组件&#xff1a;服务器Server&#xff0c;服务Service&#xff0c;连接器Connector、容器Container。连接器Connector和容器Container是Tomcat的核心。一个Container…...

前端学习-盒子模型(十八)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 盒子模型组成 边框 语法 边框简写 代码示例 表格的细线边框 语法 内边距 内边距复合写法 外边距 外边距典型应用 外边距合并 清除内外边距 总结 前…...

【C++】类和对象(十二):实现日期类

大家好&#xff0c;我是苏貝&#xff0c;本篇博客带大家了解C的实现日期类&#xff0c;如果你觉得我写的还不错的话&#xff0c;可以给我一个赞&#x1f44d;吗&#xff0c;感谢❤️ 目录 1 /!/>/</>/<运算符重载2 /-//-运算符重载(A) 先写&#xff0c;再通过写(B…...

文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《提升系统频率支撑能力的“车-氢”柔性可控负荷协同构网控制》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…...

异或的性质

交换两个变量的值&#xff0c;不使用第三个变量。 即a3,b5,交换之后a5,b3; 有两种解法, 一种用算术算法, 一种用^(异或) a a b; b a - b; a a - b; or a a^b;// 只能对int,char… b a^b; a a^b; or a ^ b ^ a; 异或交换两个变量值的方法是利用了异或运算的特性。下面是…...

新一代Webshell管理器

工具介绍 游魂是一个开源的Webshell管理器&#xff0c;提供更为方便的界面和更为简单易用的功能&#xff0c;可配合或代替其他webshell管理器&#xff0c;帮助用户在各类渗透场景中控制目标机器。游魂不仅支持常见的一句话webshell以及常见Webshell管理器的功能&#xff0c;还…...

「iOS」——知乎日报一二周总结

知乎日报仿写 前言效果Manager封装网络请求线程冲突问题下拉刷新添加网络请求的图片通过时间戳和日期格式化获取时间 总结 前言 前两周内容的仿写&#xff0c;主要完成了首页的仿写&#xff0c;进度稍慢。 效果 Manager封装网络请求 知乎日报的仿写需要频繁的申请网络请求&am…...

windows C#-匿名类型

匿名类型提供了一种方便的方法&#xff0c;可用来将一组只读属性封装到单个对象中&#xff0c;而无需首先显式定义一个类型。 类型名由编译器生成&#xff0c;并且不能在源代码级使用。 每个属性的类型由编译器推断。 可结合使用 new 运算符和对象初始值设定项创建匿名类型。 …...

CryptoHack 简介

CryptoHack 简介 文章目录 CryptoHack 简介一、python的安装&#xff0c;运行二、ASCII码三、十六进制四、Base64五、字节和大整数六、XOR1.基本2.xor属性3.xor隐藏字节4.cryptohack——You either know, XOR you dont 一、python的安装&#xff0c;运行 二、ASCII码 chr()函数…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...