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

算法学习系列(十五):最小堆、堆排序

目录

  • 引言
  • 一、最小堆概念
  • 二、堆排序模板(最小堆)
  • 三、模拟堆

引言

这个堆排序的话,考的还挺多的,主要是构建最小堆,并且在很多情况下某些东西还用得着它来优化,比如说迪杰斯特拉算法可以用最小堆优化,然后面试和考研用的也是挺多的,总之开始吧。

一、最小堆概念

本文只讲述最小堆,其一这个用的最多,而且跟最大堆来说其实都是差不多的,就一个小于一个大于

最小堆:首先是一个完全二叉树,然后每个结点都小于或等于其两个儿子,性质:根结点是整个堆的最小值。因为父亲是最小的,然后儿子又作为其儿子的父亲,也是其最小的,所以推出堆根是最小的。

存储方式:是用数组来存的,i 号下标的儿子为 2 * i,2 * i + 1,i 号下标的父亲为 i / 2
在这里插入图片描述

STL:优先级队列就是最小堆

二、堆排序模板(最小堆)

整体思路:先构建一个最小堆,然后输出堆根,再把堆根删了,再次构建,重复往返
删除堆根:用 h[size] 覆盖 h[1] ,size-- ,down(1)
这个模板我们用例题来说明

输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数,表示整数数列。输出格式
共一行,包含 m 个整数,表示整数数列中前 m 小的数。数据范围
1≤m≤n≤105,1≤数列中元素≤109输入样例:
5 3
4 5 1 3 2输出样例:
1 2 3
#include <cstdio>
#include <cstring>
#include <iostream>using namespace std;const int N = 1e5+10;int h[N];  //h[i]代表第堆中的i号下标对应的值
int n, m, cnt;  //cnt代表堆中的数量//元素变小了,就up
void up(int u)
{while(u / 2 && h[u / 2] > h[u])  //若u>=1 并且比父亲大就交换,然后u变成父亲继续判断{swap(h[u], h[u/2]);u >>= 1;}
}//元素变大了,就down
void down(int u)  //将下标为u的元素下移
{int t = u;if(u * 2 <= cnt && h[2 * u] < h[t]) t = 2 * u;  if(u * 2 + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;  //判断最小的值tif(t != u)  //若有一个儿子比自己小{swap(h[u], h[t]);  //交换值down(t);  //再次判断这个儿子}
}int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i) scanf("%d", &h[i]);cnt = n;for(int i = cnt / 2; i; --i) down(i);  //从倒数第二层的元素开始down到根,可以构建一个最小堆while(m--){printf("%d ", h[1]);  //每次都是堆根的元素最小swap(h[1], h[cnt]);cnt--;down(1);}return 0;
}

在这里插入图片描述

三、模拟堆

我们还是用例题来说明
然后这个有一个要求就是要对第k个插入的元素进行操作,但是我们又不知道第k个元素是谁,只知道下标,所以得维护两个数组ph[i] ,hp[i],代表ph[k] == i,hp[i] == k,h[i] == a

维护一个集合,初始时集合为空,支持如下几种操作:
I x,插入一个数 x;
PM,输出当前集合中的最小值;
DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
D k,删除第 k 个插入的数;
C k x,修改第 k 个插入的数,将其变为 x;现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。输入格式
第一行包含整数 N。
接下来 N 行,每行包含一个操作指令,操作指令为 I x,PM,DM,D k 或 C k x 中的一种。输出格式
对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。每个结果占一行。数据范围
1≤N≤105
−109≤x≤109
数据保证合法。输入样例:
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM输出样例:
-10
6
#include <cstdio>
#include <cstring>
#include <iostream>using namespace std;const int N = 1e5+10;int h[N], hp[N], ph[N];
int n, cnt, idx;void swap_heap(int a, int b)
{swap(ph[hp[a]],ph[hp[b]]);swap(hp[a],hp[b]);swap(h[a], h[b]);
}void up(int u)
{while(u / 2 && h[u] < h[u / 2]){swap_heap(u, u/2);u >>= 1;}
}void down(int u)
{int t = u;if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if(t != u){swap_heap(t,u);down(t);}
}int main()
{scanf("%d", &n);while(n--){char op[5];int k, x;scanf("%s", op);if(!strcmp(op,"I")){scanf("%d", &x);cnt++, idx++;h[cnt] = x;hp[cnt] = idx, ph[idx] = cnt;up(cnt);}else if(!strcmp(op,"PM")){printf("%d\n", h[1]);}else if(!strcmp(op,"DM")){swap_heap(1,cnt);cnt--;down(1);}else if(!strcmp(op,"D")){scanf("%d", &k);k = ph[k];swap_heap(k, cnt);cnt--;up(k);down(k);}else{scanf("%d%d", &k, &x);k = ph[k];h[k] = x;up(k);down(k);}}return 0;
}

在这里插入图片描述

相关文章:

算法学习系列(十五):最小堆、堆排序

目录 引言一、最小堆概念二、堆排序模板&#xff08;最小堆&#xff09;三、模拟堆 引言 这个堆排序的话&#xff0c;考的还挺多的&#xff0c;主要是构建最小堆&#xff0c;并且在很多情况下某些东西还用得着它来优化&#xff0c;比如说迪杰斯特拉算法可以用最小堆优化&#…...

HCIA-Datacom题库(自己整理分类的)——OSPF协议多选

ospf的hello报文功能是 邻居发现 同步路由器的LSDB 更新LSA信息 维持邻居关系 下列关于OSPF区域描述正确的是 在配置OSPF区域正确必须给路由器的loopback接配置IP地址 所有的网络都应在区域0中宣告 骨干区域的编号不能为2 区域的编号范围是从0.0.0.0到255.255.255.255…...

elasticsearch-hadoop.jar 6.8版本编译异常

## 背景 重新编译 elasticsearch-hadoop 包&#xff1b; GitHub - elastic/elasticsearch-hadoop at 6.8 编译 7.17 版本时很正常&#xff0c;注意设置下环境变量就好&#xff0c;JAVA8_HOME/.... 编译 6.8 版本时&#xff08;要求jdk8 / jdk9&#xff09;&#xff0c;出现…...

面试经典150题(50-53)

leetcode 150道题 计划花两个月时候刷完&#xff0c;今天&#xff08;第二十二天&#xff09;完成了4道(50-53)150&#xff1a; 50.&#xff08;141. 环形链表&#xff09;题目描述&#xff1a; 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个…...

Jetpack Compose中使用Android View

使用AndroidView创建日历 Composable fun AndroidViewPage() {AndroidView(factory {CalendarView(it)},modifier Modifier.fillMaxWidth(),update {it.setOnDateChangeListener { view, year, month, day ->Toast.makeText(view.context, "${year}年${month 1}月$…...

《MySQL》事务篇

事务特性 ACID Atomicity原子性&#xff1a;事务中的操作要么全部完成&#xff0c;要么全部失败。 Consistency一致性&#xff1a;事务操作前后&#xff0c;数据满足完整性约束。 Isolation隔离性&#xff1a;允许并发执行事务&#xff0c;每个事务都有自己的数据空间&…...

高阶组件和高阶函数是什么

高阶组件和高阶函数都是在函数式编程中常见的概念。 高阶组件&#xff08;Higher-Order Component, HOC&#xff09;是一种函数&#xff0c;接受一个组件作为参数&#xff0c;并返回一个新的组件。它可以用来增强现有的组件&#xff0c;给它添加额外的功能或属性。高阶组件在R…...

初步认识API安全

一、认识API 1. 什么是API API(应用程序接口)&#xff1a;是一种软件中介&#xff0c;它允许两个不相关的应用程序相互通信。它就像一座桥梁&#xff0c;从一个程序接收请求或消息&#xff0c;然后将其传递给另一个程序&#xff0c;翻译消息并根据 API 的程序设计执行协议。A…...

MybatisX逆向工程方法

官方文档链接&#xff1a;MybatisX快速开发插件 | MyBatis-Plus (baomidou.com) 使用MybatisX可以快速生成mapper文件&#xff0c;实体类和service及实现 效果 方法&#xff1a;首先下载mybatisX插件 然后创建数据库信息 然后选中表&#xff0c;右键&#xff0c;点击Mybatis…...

每日一题:LeetCode-LCR 179. 查找总价格为目标值的两个商品

每日一题系列&#xff08;day 16&#xff09; 前言&#xff1a; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f50e…...

SpringBoot 3.2.0 基于Logback定制日志框架

依赖版本 JDK 17 Spring Boot 3.2.0 工程源码&#xff1a;Gitee 日志门面和日志实现 日志门面&#xff08;如Slf4j&#xff09;就是一个标准&#xff0c;同JDBC一样来制定“规则”&#xff0c;把不同的日志系统的实现进行了具体的抽象化&#xff0c;只提供了统一的日志使用接…...

微软发布安卓版Copilot,可免费使用GPT-4、DALL-E 3

12月27日&#xff0c;微软的Copilot助手&#xff0c;可在谷歌应用商店下载。目前&#xff0c;只有安卓版&#xff0c;ios还无法使用。 Copilot是一款类ChatGPT助手支持中文&#xff0c;可生成文本/代码/图片、分析图片、总结内容等&#xff0c;二者的功能几乎没太大差别。 值…...

【STM32】程序在SRAM中运行

程序在RAM中运行 1、配置内存分配。 2、修改跳转文件 FUNC void Setup(void) { SP _RDWORD(0x20000000); PC _RDWORD(0x20000004); } LOAD RAM\Obj\Project.axf INCREMENTAL Setup(); 3、修改下载ROM地址和RAM地址&#xff1b; 中断向量表映射 中断向量表映射到SRA…...

docker 部署mysql

docker pull mysql:5.7.25 docker run \ --name mysql \ -e MYSQL_ROOT_PASSWORD123456 \ -p 3306:3306 \ -v /soft/mysql/conf:/etc/mysql \ -v /soft/mysql/data:/var/lib/mysql \-d \mysql:5.7.25安装好之后可以用命令行进入查看 docker exec -it mysql mysql -u root -p密…...

科荣AIO ReportServlet存在目录遍历漏洞

文章目录 产品简介漏洞概述指纹识别漏洞利用修复建议 产品简介 科荣AIO是一款企业管理软件&#xff0c;提供企业一体化管理解决方案。它整合了ERP&#xff08;如进销存、财务管理&#xff09;、OA&#xff08;办公自动化&#xff09;、CRM&#xff08;客户关系管理&#xff09…...

Ubuntu Desktop 22.04 桌面主题配置

Ubuntu Desktop 22.04 桌面主题配置 使用这么久 Ubuntu Desktop&#xff0c;本着不折腾的原则&#xff0c;简单介绍下自己的桌面主题配置。 安装 tweaks 安装 GNOME Shell 安装 GNOME theme安装 gnome-tweaks & chrome-gnome-shell sudo apt update # 安装 gnome-tweaks…...

SuperMap iServer发布的ArcGIS REST 地图服务如何通过ArcGIS API进行要素查询

作者&#xff1a;yx 前言 前面我们介绍了SuperMap iServer发布的ArcGIS REST 地图服务如何通过ArcGIS API加载&#xff0c;这里呢我们再来看看如何进行要素查询呢&#xff1f; 一、服务发布 SuperMap iServer发布的ArcGIS REST 地图服务如何通过ArcGIS API加载已经介绍如何发…...

H5向微信小程序发送信息(小程序web-view打开H5)

引入weixin-js-sdk npm i weixin-js-sdk 页面引入 // 引入wxjsimport wx from "weixin-js-sdk"; 点击触发方法 methods: {goweap(id){console.log(wx);// H5传递数据 &#xff08;navigateBack&#xff09;wx.miniProgram.navigateBack({delta: 1});wx.min…...

白话机器学习的数学-1-回归

1、设置问题 投入的广告费越多&#xff0c;广告的点击量就越高&#xff0c;进而带来访问数的增加。 2、定义模型 定义一个函数&#xff1a;一次函数 y ax b &#xff08;a 是斜率、b 是截距&#xff09; 定义函数&#xff1a; 3、最小二乘法 例子&#xff1a; 用随便确定的参…...

ubuntu22下安装minconda

bing 搜索 canda install 找到官方网站 https://docs.conda.io/projects/miniconda/en/latest/ 这里我们安装minconda。 官网有安装方法。 mkdir -p ~/miniconda3 wget https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh -O ~/miniconda3/miniconda.sh…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...