【数据结构】堆的应用(小根堆)

news/2024/2/22 19:11:55

知识概览

堆用来维护一个数据集合。堆是一个二叉树,可以说是二叉树的一个应用,堆还是一个完全二叉树。

小根堆:每个点都满足它小于等于左右两边的点。

一维数组用来存下来一棵树。在堆中,x的左儿子是2x,右儿子是2x + 1,1号点是根节点。

如何手写一个堆?

  1. 插入一个数:heap[++size] = x; up(size);
  2. 求集合当中的最小值:heap[1];
  3. 删除最小值:heap[1] = heap[size]; size--; down(1);
  4. 删除任意一个元素:heap[k] = heap[size]; size--; down(k); up(k);
  5. 修改任意一个元素:heap[k] = x; down(k); up(k);

其中,down(x)表示在一个小根堆中,当一个数变大之后往下调整;up(x)表示在一个小根堆中,当一个数变小之后往上调整。1-3操作在C++的STL中的priority_queue中有实现,但是4、5需要间接实现,这是手写堆的一个好处,在Dijkstra(迪杰斯特拉)算法的堆优化中会有用到。

例题展示

题目链接

https://www.acwing.com/problem/content/840/

代码

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n, m;
int h[N], cnt;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 (u != t){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 = n / 2; i; i--) down(i);while (m--){printf("%d ", h[1]);swap(h[1], h[cnt--]);down(1);}return 0;
}

题目链接

https://www.acwing.com/problem/content/841/

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 100010;int h[N], ph[N], hp[N], cnt;void heap_swap(int a, int b)
{swap(ph[hp[a]], ph[hp[b]]);swap(hp[a], hp[b]);swap(h[a], h[b]);
}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 (u != t){heap_swap(u, t);down(t);}
}void up(int u)
{while (u / 2 && h[u] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;}
}int main()
{int n, m = 0;scanf("%d", &n);while (n--){char op[5];int k, x;scanf("%s", op);if (!strcmp(op, "I")){scanf("%d", &x);cnt++;m++;ph[m] = cnt, hp[cnt] = m;h[cnt] = x;up(cnt);}else if (!strcmp(op, "PM")) printf("%d\n", h[1]);else if (!strcmp(op, "DM")){heap_swap(1, cnt);cnt--;down(1);}else if (!strcmp(op, "D")){scanf("%d", &k);k = ph[k];heap_swap(k, cnt);cnt--;down(k), up(k);}else{scanf("%d%d", &k, &x);k = ph[k];h[k] = x;down(k), up(k);}}
}


https://dhexx.cn/news/show-5177712.html

相关文章

hdlbits系列verilog解答(mt2015_q4)-54

文章目录 一、问题描述二、verilog源码三、仿真结果一、问题描述 本次使用系列文章52和53中实现的子模块,实现以下组合逻辑电路。 二、verilog源码 module top_module (input x, input y, output z);wire [3:0

RocketMQ-源码架构二

梳理一些比较完整&#xff0c;比较复杂的业务线 消息持久化设计 RocketMQ的持久化文件结构 消息持久化也就是将内存中的消息写入到本地磁盘的过程。而磁盘IO操作通常是一个很耗性能&#xff0c;很慢的操作&#xff0c;所以&#xff0c;对消息持久化机制的设计&#xff0c;是…

spring集成mybatis简单教程

首先说下实现了什么效果&#xff0c;就是不用每次查询前手动创建 sessionFactory和添加datasource文件了。 整个工程结构是这样的 这次我也把代码放在了gitee上&#xff0c;方便大家更全貌的看到所有的实现细节。代码链接如下&#xff1a; Java: 一些Java代码 (gitee.com) …

2024年网络安全竞赛-网站渗透

网站渗透 (一)拓扑图 1.使用渗透机对服务器信息收集,并将服务器中网站服务端口号作为flag提交; 使用nmap工具对靶机进行信息收集 2.使用渗透机对服务器信息收集,将网站的名称作为flag提交; 访问页面即可 3.使用渗透机对服务器渗透,将可渗透页面的名称作为flag提交…

利用Node.js和cpolar实现远程访问,无需公网IP和路由器设置的完美解决方案

文章目录 前言1.安装Node.js环境2.创建node.js服务3. 访问node.js 服务4.内网穿透4.1 安装配置cpolar内网穿透4.2 创建隧道映射本地端口 5.固定公网地址 前言 Node.js 是能够在服务器端运行 JavaScript 的开放源代码、跨平台运行环境。Node.js 由 OpenJS Foundation&#xff0…

【链表Linked List】力扣-114 二叉树展开为链表

目录 题目描述 解题过程 官方题解 题目描述 给你二叉树的根结点 root &#xff0c;请你将它展开为一个单链表&#xff1a; 展开后的单链表应该同样使用 TreeNode &#xff0c;其中 right 子指针指向链表中下一个结点&#xff0c;而左子指针始终为 null 。展开后的单链表应…

Python开发运维:Python垃圾回收机制

目录 一、理论 1.Python垃圾回收机制 一、理论 1.Python垃圾回收机制 &#xff08;1&#xff09;引⽤计数器 1&#xff09;环状双向链表 refchain 在python程序中创建的任何对象都会放在refchain链表中。 name "david" age 20 hobby ["篮球",游泳…

【小聆送书第二期】人工智能时代之AIGC重塑教育

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;网络奇遇记、数据结构 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;正文&#x1f4dd;活动参与规则 参与活动方式文末详见。 &#x1f4cb;正文 AI正迅猛地…

uniapp图片预览

用的是Uview组件库里面的 直接在页面写上&#xff1a; <u-album singleSize"100" :urls"[https://lxt.jingyi.icu/item.img]"></u-album> 这图片路径是我自己的 你们可以按照组件库里面的方法去实现

【PyTorch】模型选择、欠拟合和过拟合

文章目录 1. 理论介绍2. 实例解析2.1. 实例描述2.2. 代码实现2.2.1. 完整代码2.2.2. 输出结果 1. 理论介绍 将模型在训练数据上拟合的比在潜在分布中更接近的现象称为过拟合&#xff0c; 用于对抗过拟合的技术称为正则化。训练误差和验证误差都很严重&#xff0c; 但它们之间差…