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

【数据结构】堆

news 来源：原创 2025/5/15 5:00:47

一、堆

二、堆的模拟实现

1.结构体

2.push

3.pop和top

三.实现堆排序

1.成堆算法

2.堆排序

heap模拟实现源码_gitee

一、堆

分为大堆和小堆

大堆是每个父节点都大于子节点，小堆则相反是每个父节点都小于子节点

底层抽象结构是完全二叉树，下面实现方式底层是数组

二、堆的模拟实现

1.结构体

typedef int hptype;typedef struct heap
{hptype* data;int size;int capacity;}hp;void hpinit(hp* x)
{assert(x);x->data = NULL;x->capacity = x->size = 0;}void hpdestory(hp* x)
{assert(x);free(x->data);x->data = NULL;x->capacity = x->size = 0;}

上面的typedef是为了方便改动

2.push

void swap(hptype* p1, hptype* p2)
{hptype tmp = *p1;*p1 = *p2;*p2 = tmp;}//把底下不符合堆的进行调整
//小堆
void adjustup(hptype* data, int child)
{assert(data);int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else { break; }}}
void hppush(hp* p, hptype x)
{assert(p);if (p->capacity == p->size){int num = p->capacity == 0 ? 4 : p->capacity * 2;hptype* newdata = (hptype*)realloc(p->data, sizeof(hptype) * num);if (newdata == NULL){perror("newdata==null");return;}p->data = newdata;p->capacity = num;}p->data[p->size++] = x;adjustup(p->data, p->size - 1);}

3.pop和top

void adjustdown(hptype* data, int size, int parent)
{assert(data);int small = parent * 2 + 1;while (small < size)
{  if(small+1<size&&data[small]>data[small+1]){small++;}if (data[parent] > data[small]){swap(&data[parent], &data[small]);parent = small;small = parent * 2 + 1;}else { break; }}}
void hppop(hp* x)
{assert(x);assert(x->size > 0);swap(&x->data[0], &x->data[x->size - 1]);x->size--;adjustdown(x->data, x->size, 0);}hptype hptop(hp*x)
{assert(x);return x->data[0];
}bool hpempty(hp*x)
{assert(x);return x->size == 0;
}

pop是实现的把堆顶pop,还要保持堆的形象

应用：实现top_k个最小数的打印

思路：先将数据建堆，在获取top后pop，循环k次

void test2()
{int a[] = { 10,2,99,4,5,9,7,8,6, };hp x;hpinit(&x);for (int i=0;i<9;i++){hppush(&x, a[i]);}int k = 0;scanf("%d", &k);while(k--){printf("%d ", hptop(&x));hppop(&x);}}

三.实现堆排序

1.成堆算法

1.adjustup+for;

2.adjustdown+for

实例逻辑是小堆

void adjustup(hptype* data, int child)
{assert(data);int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else { break; }}}void adjustdown(hptype* data, int size, int parent)
{assert(data);int small = parent * 2 + 1;while (small < size)
{  if(small+1<size&&data[small]>data[small+1]){small++;}if (data[parent] > data[small]){swap(&data[parent], &data[small]);parent = small;small = parent * 2 + 1;}else { break; }}}

for正序遍历+adjustup,时间复杂度 nlogn

void test3(){int a[10] = { 2,3,1,5,6,7,0,39,99,33 };for(int i=1;i<10;i++){adjustup(a, i);}for(int  i=0;i<10;i++){printf("%d ", a[i]);}}

for从叶子节点的父节点遍历+adjustdown

void test4() {int a[10] = { 2,3,1,5,6,7,0,39,99,33 };for (int i = (10-1-1)/2;i >=0;i--){adjustdown(a, 10,i);}for (int i = 0;i < 10;i++){printf("%d ", a[i]);}}

*调整算法复杂度讨论

adjustup+for

adjustdown+for

2.堆排序

底层思想是先成堆，在取堆顶数与末尾交换，即此时末尾一定是最大或最小，再以此类推

void heapsort(hptype *x,int n)
{assert(x);for(int i=1;i<n;i++){adjustup(x, i);}int end = n - 1;while(end>0){swap(&x[0], &x[end]);adjustdown(x, end, 0);end--;}}

堆排序的升降是由堆是大小堆决定的，如果建成大堆，那么顶就是最大，取到队尾就是升序

如果小堆，取到队尾就是降序

升序=>大堆

降序=>小堆

*堆排序中while+adjustdown复杂度

四.*topk问题

求一堆数据中最大的前k个，这k个返回时不需要之间大小排序

思路1：直接对数据建大堆，顶上为最大，接着pop+top继续

时间复杂度：建堆O（n）+pop_topO( k*log(N) ) =>O（n）

空间复杂度：建堆O（n）

思路2：建k小堆，比顶上大的就顶上交换，然后再调整堆，以此类推

时间复杂度：建堆O（K）+遍历O(N-K) =>O( n )

空间复杂度：O(K)

void topk()
{int k = 0;scanf("%d", &k);int* kmax = (int*)malloc(k * sizeof(int));FILE* fout = fopen("data.txt", "r");//先取k个数进行建堆for(int i=0;i<k;i++){fscanf(fout, "%d", &kmax[i]);}for(int i=(k-1-1)/2;i>=0;i--){adjustdown(kmax, k, i);}int x = 0;
//打开文件开始遍历比较while(fscanf(fout,"%d",&x)>0){if(x>kmax[0]){kmax[0] = x;adjustdown(kmax, k, 0);}}//打印for(int i=0;i<k;i++){printf("%d ", kmax[i]);}}

【数据结构】堆

目录一、堆二、堆的模拟实现 1.结构体 2.push 3.pop和top 三.实现堆排序 1.成堆算法 2.堆排序 heap模拟实现源码_gitee 一、堆分为大堆和小堆大堆是每个父节点都大于子节点，小堆则相反是每个父节点都小于子节点底层抽象结构是完全二叉树&#xff0…...

编程日记 2025/5/15 5:00:47

6.824/6.5840 Lab 1: MapReduce

宁静的夏天天空中繁星点点心里头有些思念思念着你的脸 ——宁夏完整代码见： https://github.com/SnowLegend-star/6.824 由于这个lab整体难度实在不小，故考虑再三还是决定留下代码仅供参考 6.824的强度早有耳闻，我终于也是到了挑战这座高…...

编程日记 2025/5/15 4:58:40

Day5：生信新手笔记 — R语言基本语法

一、数据类型 （重点只有两个，剩下的不看） 1.1 向量（vector） 矩阵（Matrix） 数组（Array） 1.2 数据框（Data frame） x<- c(1,2,3) #常用的向…...

编程日记 2025/5/11 0:06:51

lua download

https://www.lua.org/ https://www.lua.org/versions.html#5.4...

编程日记 2025/5/15 4:57:33

安装更新upgrade导致ubuntu崩溃

安装更新导致ubuntu崩溃前言uuid编不过，导致的崩溃记录一些ubuntu崩溃的过程。目前只有一个，以后遇到都放在这里，以提醒自己。前言如果从10000年看现在的linux，不是说不完美，而是糟透了。 linux的版本号&#xf…...

编程日记 2025/5/14 5:36:48

软件测试最新项目合集【商城、外卖、银行、金融等等.......】

项目一：ShopNC商城项目概况： ShopNC商城是一个电子商务B2C电商平台系统，功能强大，安全便捷。适合企业及个人快速构建个性化网上商城。包含PCIOS客户端Adroid客户端微商城，系统PC后台是基于ThinkPHP MVC构架开发的跨…...

编程日记 2025/5/15 4:17:37

【学习总结|DAY09】Java 流程控制与数据操作练习一：录入三位数并筛选符合条件的数字

一、主要代码： import java.util.Scanner;public class demo07 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);System.out.print("请输入一个大于100的三位数：");int number scanner.nextInt();if (nu…...

编程日记 2025/5/15 4:23:07

“放弃Redis Desktop Manager使用Redis Insight”：日常使用教程(Redis可视化工具)

文章目录更新Redis Insight连接页面基础解释自动更新key汉化暂时没有找到方法， Redis Desktop Manager在连接上右键在数据库上右键在key上右键1、添加连接2、key过期时间参考文章更新 (TωT)ﾉ~~~ βｙё βｙё~ 现在在维护另一…...

编程日记 2025/5/15 4:08:11

使用lumerical脚本语言创建弯曲波导并进行数据分析（纯代码实现）

本文使用lumerical脚本语言创建弯曲波导、设置有限差分时域（FDTD）模拟、改变波导弯曲半径计算损耗、绘制图像展示电场强度分布情况及对具有不同弯曲半径的波导进行一系列模拟和分析操作（代码均有注释讲解）。一、创建弯曲波导 1.1 基本结构讲解（1）包层（Clad）在波导结…...

编程日记 2025/5/15 4:27:37

AC+AP漫游实验

实验拓扑实验要求 1.AP1服务vlan10，AP2服务vlan20，实现三层漫游 2.AP1与AP2为不同AP组，直接转发实验步骤 1.配置VLAN放行相关流量交换机与AP接口为trunk口并修改PVID为30 2.配置相关业务使得ap上线 3.配置vap上线，AP可用…...

编程日记 2025/5/13 20:00:45

七：仪表盘安装-controller node

一：工具、环境准备-controller node 二：OpenStack环境准备-controller node 三：安装服务-controller node 四：工具、环境准备-compute node 五：OpenStack环境准备-compute node 六：安装服务-compute node 七…...

编程日记 2025/5/12 8:52:23

pandas习题 067：小于 60 的部分列修改为 60

（编码题）修改以下名为 df 的 DataFrame 的值，将 Q1、Q2、Q3、Q4 列中小于 60 的分数修改为 60。 import pandas as pd# 示例数据 data = {name: [Alice, Bob, Charlie],...

编程日记 2025/4/29 16:46:18

Flutter 版本管理工具FVM

FVM是一款非常好用的Flutter版本管理工具。FVM官网： 下面是使用 FVM（Flutter Version Manager）管理 Flutter 版本的整个流程，包括安装、配置环境变量以及基本的使用步骤。 1. 安装 FVM FVM 可以通过多种方式安装，下…...

编程日记 2025/5/15 4:42:38

图学习GNN笔记

目录第一部分：预测分析中的图学习4.3 案例研究：图上的学习机器学习生命周期第二部分：图特征学习特征表示与嵌入为什么难以学习？ 第三部分：节点嵌入嵌入节点设置学习节点嵌入浅层编码如何定义节点相似性？ …...

编程日记 2025/5/15 3:35:15

装饰器—购物打折

from collections import namedtuple# 定义促销策略列表 promos []# 装饰器函数，用于注册促销策略 def promotion(promo_func):promos.append(promo_func)return promo_func# 促销策略1：忠诚度积分折扣 promotion def fidelity(order):""&quo…...

编程日记 2025/5/15 4:28:42

【Linux---10】本地机器＜=＞服务器文件互传

文章目录 1. 小文件互传2. 大文件互传 1. 小文件互传使用sz命令。说明：sz命令是ZModem文件传输协议的一部分，用于在Linux和Unix系统中，从本地系统发送（send）文件到远程系统。sz命令通常与rz命令（ZModem接…...

编程日记 2025/5/12 4:03:33

Mysql数据库基础篇笔记

目录 sql语句 DDL——数据库定义语言（定义库，表，字段） 数据库操作： 表操作： DML 增删改语句 DQL 语法编写顺序： 条件查询 DCL 用户管理： 权限管理： 函数常见字符串内置函…...

编程日记 2025/5/5 2:31:52

QT 实现QStackedWidget切换页面右移动画

1.实现效果以下是一个QStackedWidget，放了两个QPushButton在上面，点击切换不同的界面。为了方便查看动画特效，设置了每个界面的背景图片。 2.实现思路首先截取当前界面的图片，渲染到一个QLabel上，然后设置QPropertyAnimation动画，动画的作用对象就是这个QLabel，不断…...

编程日记 2025/5/13 5:38:43

RocketMQ rocketmq-tools管理主题

RocketMQ rocketmq-tools管理主题环境和软件版本增删改查环境和软件版本 Win10、IDEA、Jdk1.8、rocketmq 5.1.3、rocketmq-tools 5.1.3 引入依赖 <dependency><groupId>org.apache.rocketmq</groupId><artifactId>rocketmq-tools</artifactId&g…...

编程日记 2025/5/15 4:32:08

Docker 容器隔离关键技术：Seccomp

Docker 容器隔离关键技术：Seccomp 在 Docker 容器中，Seccomp（Secure Computing Mode） 是一种内核安全机制，用来限制容器内的程序可以调用哪些系统调用（Syscalls）。通过列清单的方式&#xff0c…...

编程日记 2025/5/15 4:40:07

2024年顶级小型语言模型前15名

本文，我们将深入了解2024年备受瞩目的十五款小型语言模型（SLMs），它们分别是Llama 3.1 8B、Gemma2、Qwen 2、Mistral Nemo、Phi-3.5等。这些SLMs以其精巧的体积和高效率著称，它们不需要依赖庞大的服务器资源&#xff0c…...

编程日记 2025/5/4 11:22:56

【大模型微调】pdf转markdown

目前市面上大部分都是pdf文档，要想转换成能训练的文本，调研了各种工具。觉得MinerU确实不错。参考此链接进行操作 MinerU/docs/README_Ubuntu_CUDA_Acceleration_en_US.md at master opendatalab/MinerU GitHub 需要注意的几个点： 1. 使用root账户安装的，配置文件在…...

编程日记 2025/5/15 4:33:40

【Nacos02】消息队列与微服务之Nacos 单机部署

Nacos 部署 Nacos 部署说明 Nacos 快速开始 Nacos 快速开始版本选择当前推荐的稳定版本为2.X Releases alibaba/nacos GitHuban easy-to-use dynamic service discovery, configuration and service management platform for building cloud native applications. - Re…...

编程日记 2025/5/12 11:22:38

PROTEUS资源导引

本专栏讲述51、32单片机的仿真设计，且所有文章资源共享，如需哪篇文章，可按ctrlF键搜索查询，点击进入即可。 -----------------------------------------------------------目录------------------------------------------------…...

编程日记 2025/5/15 5:00:47

对力扣77组合优化的剪枝操作的理解

77. 组合代码随想录放出了这一张图我乍一看觉得想当然,但是仔细想想,又不知道以下剪枝代码作何解释,因此我想通过这篇文章简要解释一下 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int sta…...

编程日记 2025/5/11 6:17:16

FFmpeg 4.3 音视频-多路H265监控录放C++开发十九，ffmpeg封装

封装就是将一个h264，和一个aac文件重新封装成一个mp4文件。这里我们的h264 和 aac都是来源于另一个mp4文件，也就是说，我们会将 in.mp4文件解封装成一路videoavstream 和一路 audioavstream，然后将这两路的 avstream 合并成一…...

编程日记 2025/5/6 7:09:13

http 与 https 汇总

文章目录 http 与 httpsHTTP（超文本传输协议）介绍1. 基本概念2. 工作原理3. 特点4. 应用场景 HTTPS（超文本传输安全协议）介绍1. 基本概念2. 工作原理3. 特点4. 应用场景 HTTP协议的工作原理请求阶段响应阶段客户端解析处理协议的…...

编程日记 2025/5/15 4:33:40

龙蜥 Linux 安装 Nginx

龙蜥 Linux 安装 Nginx 下载编译安装配置编译参数先装依赖编译安装使用启动检查配置文件重启关闭 503权限问题参考资料下载下载地址详情见参考资料，我下的 nginx-1.26.2.tar.gz 到 /home/jerry/ /home/jerry$ curl -O http://nginx.org/download/nginx-1.26.2.…...

编程日记 2025/5/15 4:20:05

8. 一分钟读懂“代理模式”

8.1 模式介绍代理模式是一种结构型设计模式，它通过提供一个代理对象来替代对另一个对象（真实对象）的访问。代理对象与真实对象实现相同的接口，并通过代理类对真实对象的访问进行控制，可以在调用前后执行附加操作&…...

编程日记 2025/5/14 9:42:05

分布式搜索引擎Elasticsearch

Elasticsearch是一个基于Lucene库的开源分布式搜索引擎，它被设计用于云计算中，能够实现快速、near-real-time的搜索，并且可以进行大规模的分布式索引。以下是一个简单的Python代码示例，展示如何使用Elasticsearch的Python客户端…...

编程日记 2025/5/15 4:55:21

完全按照手册win10里装Ubuntu 虚拟机然后编译ESP32（主要是想针对ESP32C3和S3）开发板的鸿蒙系统(失败)

基本上完全按照手册来的，除了Ubuntu虚拟机使用了22.04 Jammy版本，鸿蒙手册里是20.04 版本，主要是鸿蒙里3年前的手册了，所以就擅自用了高版本。据此还想到一点，鸿蒙LiteOS，还挺稳定的，3年也没有…...

编程日记 2025/5/15 4:12:07

MySQL 8.0与PostgreSQL 15.8的性能对比

以下是MySQL 8.0与PostgreSQL 15.8的性能对比： MySQL 8.0性能特点： MySQL在处理大量读操作时表现出色，其存储引擎InnoDB提供了行级锁定和高效的事务处理，适用于并发读取的场景。MySQL通过查询缓存来提高读取性能，查询缓…...

编程日记 2025/5/15 4:37:40

hive 行转列

行转列的常规做法是，group bysum(if())【或count(if())】建表: CREATE TABLE table2 (year INT,month INT,amount DOUBLE );INSERT INTO table2 (year, month, amount) VALUES(1991, 2, 1.2),(1991, 3, 1.3),(1991, 4, 1.4),(1992, 1, 2.1),(1992, 2, 2.2),(1992…...

编程日记 2025/5/15 1:15:49

linux——进程间通信system V消息队列

Linux——命名管道及日志-CSDN博客文章目录目录文章目录前言一、system V消息队列是什么？ 二、相关库接口 1.shmget接口 2、ftok接口 3、shmget、ftok接口封装 4、共享内存操作编辑 5、shmdt接口三.函数的调用 1、查看共享内存 2、shell 四…...

编程日记 2025/5/14 4:36:24

Seatunnel解决ftp读取json文件无法读取数组以及格式化之后的json无法解析的问题

问题原因在JsonRead这个方法里面在源码中使用的逻辑是读取一行然后把这个json进行解析但是这样存在一个问题比如如果json的格式是这样的 { name：“zhangsan”， age：25 } 如果是这样的话第一行读到的内容就是 { 显然一个 { 并不是一个…...

编程日记 2025/5/15 4:30:52

[Vue Router warn]: No match found for location with path 解决方法

在使用vue3 vue-router4时当列表A组件使用加上keep-alive缓存后，跳转至详情页面时出现 [Vue Router warn]: No match found for location with path "/atlas/editDetails" 解决方案： 把 router.push({ path: "/atlas/editDetails&…...

编程日记 2025/5/14 23:05:41

优傲协作机器人 Remote TCP Toolpath URCap（操作记录）

目录一、新机设置项 1、设置管理员密码 2、设置安全密码 3、设置负载二、激活 Remote TCP & Toolpath URCap 1、插入U盘 2、打开激活面板 3、导入许可证 4、查看是否激活成功 5、启用功能三、使用流程（官方） 步骤一步骤二步骤三 …...

编程日记 2025/5/15 4:25:27

使用历史索引监控 Elasticsearch 索引生命周期管理

作者：来自 Elastic Stef Nestor 大家好！在之前的一篇博客中，我们概述了常见的索引生命周期管理 (index lifecycle management - ILM) 问题及其解决方案。此后，我们已将这些常见场景添加到我们的 Elasticsearch 文档中，…...

编程日记 2025/5/15 4:12:07

[网络安全]sqli-labs Less-5 解题详析

[网络安全]Less-5 GET - Double Injection - Single quotes - String:双注入GET单引号字符型注入判断注入类型判断注入点个数查库名（爆破） left函数抓包查库名（双查询注入） 原理实例查库名（extractvalue函数&#xff…...

编程日记 2025/5/10 8:32:27

贪心算法入门（一）

第1题礼物查看测评数据信息国庆马上要到了。小明喜欢的礼物有n种分别是：公仔、电子手表、漫画书等。每种礼物有一件，每种礼物价钱都不一样。小明手头上有 m 元。小明最多可以买多少件礼物？ 输入格式第一行，两个整数&…...

编程日记 2025/5/15 4:16:21

HTTP 探秘之旅：从入门到未来

文章目录导言：目录：第一篇：HTTP，互联网的“快递员”第二篇：从点开网页到看到内容，HTTP 究竟做了什么？第三篇：HTTP 的烦恼与进化史第四篇：HTTP 的铠甲——HTTPS 的故事第…...

编程日记 2025/5/15 4:01:59

网络安全技术详解：虚拟专用网络（VPN）安全信息与事件管理（SIEM）

虚拟专用网络（VPN）详细介绍虚拟专用网络（VPN）通过在公共网络上创建加密连接来保护数据传输的安全性和隐私性。工作原理 VPN的工作原理涉及建立安全隧道和数据加密： 隧道协议：使用协议如PPTP、L2TP/IP…...

编程日记 2025/5/11 8:02:41

人工智能中的深度学习：原理与实践

什么是深度学习？ 深度学习（Deep Learning）是机器学习的一个分支，旨在通过模拟人脑的神经网络结构来解决复杂的任务。深度学习通过多层神经网络，自动从数据中学习特征，避免了传统机器学习中手动特征工程的繁…...

编程日记 2025/5/7 8:03:23

复现SMPLify-X: Ubuntu22.04, Cuda-11.3, GPU=3090Ti

Env: 3090Ti CUDA 最低支持版本需要>cuda-11.1 Ubuntu 22.04 Installation: Installing CUDA11.3 wget https://developer.download.nvidia.com/compute/cuda/11.3.0/local_installers/cuda_11.3.0_465.19.01_linux.run sudo sh cuda_11.3.0_465.19.01_linux.run …...

编程日记 2025/5/12 17:26:43

qt QGraphicsScale详解

1、概述 QGraphicsScale是Qt框架中提供的一个类，它提供了一种简单而灵活的方式在QGraphicsView框架中实现缩放变换。通过设置水平和垂直缩放因子、缩放中心点，可以创建各种缩放效果，提升用户界面的交互性和视觉吸引力。结合QPropertyAnimati…...

编程日记 2025/5/13 3:04:57

全新首发小利特惠/生活缴费/电话费/油卡燃气/等充值业务类源码附带U商承兑系统

全新首发小利特惠/生活缴费/电话费/油卡燃气/等充值业务类源码附带U商承兑系统 php7.4及以上 / mysql5.6 / 伪静态：thinkphp / 运行目录：/public / 修改数据库：/config/database.php /后台：/admin 账号密码 admin q2821706481 …...

编程日记 2025/5/12 12:19:43

ubuntu 根分区逻辑卷扩容

1、虚拟机关机通过管理界面给磁盘扩容。 rootcurtis:/home/curtis/git_code# pvdisplay--- Physical volume ---PV Name /dev/vda3VG Name ubuntu-vgPV Size <239.00 GiB / not usable 0Allocatable yes (but full)PE…...

编程日记 2025/5/10 22:50:24