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

2023-12-11 03:52

本文主要是介绍【数据结构】堆的应用(小根堆),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

知识概览

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

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

一维数组用来存下来一棵树。在堆中,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);}}
}

这篇关于【数据结构】堆的应用(小根堆)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/479360

相关文章

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

《SpringAI集成DeepSeek三步搞定Java智能应用的详细过程》本文介绍了如何使用SpringAI集成DeepSeek,一个国内顶尖的多模态大模型,SpringAI提供了一套统一的接口,简... 目录DeepSeek 介绍Spring AI 是什么?Spring AI 的主要功能包括1、环境准备2

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

MobaXterm远程登录工具功能与应用小结

《MobaXterm远程登录工具功能与应用小结》MobaXterm是一款功能强大的远程终端软件,主要支持SSH登录,拥有多种远程协议,实现跨平台访问,它包括多会话管理、本地命令行执行、图形化界面集成和... 目录1. 远程终端软件概述1.1 远程终端软件的定义与用途1.2 远程终端软件的关键特性2. 支持的

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

5分钟获取deepseek api并搭建简易问答应用

《5分钟获取deepseekapi并搭建简易问答应用》本文主要介绍了5分钟获取deepseekapi并搭建简易问答应用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需... 目录1、获取api2、获取base_url和chat_model3、配置模型参数方法一:终端中临时将加

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为

Python调用另一个py文件并传递参数常见的方法及其应用场景

《Python调用另一个py文件并传递参数常见的方法及其应用场景》:本文主要介绍在Python中调用另一个py文件并传递参数的几种常见方法,包括使用import语句、exec函数、subproce... 目录前言1. 使用import语句1.1 基本用法1.2 导入特定函数1.3 处理文件路径2. 使用ex

将Python应用部署到生产环境的小技巧分享

《将Python应用部署到生产环境的小技巧分享》文章主要讲述了在将Python应用程序部署到生产环境之前,需要进行的准备工作和最佳实践,包括心态调整、代码审查、测试覆盖率提升、配置文件优化、日志记录完... 目录部署前夜:从开发到生产的心理准备与检查清单环境搭建:打造稳固的应用运行平台自动化流水线:让部署像

Linux中Curl参数详解实践应用

《Linux中Curl参数详解实践应用》在现代网络开发和运维工作中,curl命令是一个不可或缺的工具,它是一个利用URL语法在命令行下工作的文件传输工具,支持多种协议,如HTTP、HTTPS、FTP等... 目录引言一、基础请求参数1. -X 或 --request2. -d 或 --data3. -H 或