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

【数据结构】优先队列

优先队列

      • API
      • 初级实现
      • 使用堆实现
        • 由下至上的堆有序化(上浮)
        • 由上至下的堆有序化(下沉)
        • 插入和删除元素
        • 具体实现

很多情况下我们需要有序的处理输入的元素,但是又不需要输入的元素全部有序,或者不需要一次将它们排序出来。还有的情况的输入的元素不是一次性给出的,需要我们根据需要实时获取最大值或者最小值。这时候我们就可以使用优先队列实现我饿们的需求。

API

public class MaxPQ <Key extends Comparable<Key>>
MaxPQ()创建一个优先队列
MaxPQ(int max)创建一个初始容量为max的优先队列
MaxPQ(Key[] a)用a[]中的元素创建一个优先队列
void insert(Key v)向优先队列中插入一个元素
Key max()返回最大元素
Key delMax()删除返回最大元素
boolean isEmpty()返回队列是否为空
int size()返回优先队列中元素个数

初级实现

初级实现是使用一个数组或者链表,在插入时或者获取最大元素动态维护数组或者链表的有序性并使得调用对应获取最大值的API能正确获取结果。

使用堆实现

当一棵二叉树的每个结点都大于等于它的两个子节点时,它被称为堆有序。根节点是堆有序的二叉树中的最大结点。二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级存储(不使用数组的第一个位置)

由下至上的堆有序化(上浮)

如果堆有序的状态因为某个节点变得比它的父节点更大而被打破,那么我们就需要通过交换它和它的父节点来修复堆。交换后,这个节点比它的两个子节点都打,但这个节点仍然可能比它现在的父节点更大。我们可以一遍遍地使用同样地办法恢复秩序,将这个节点不断向上移动直到我们遇到一个更大的父节点。

private void swim(int k) {while (k > 1 && less(k / 2, k)) {exch(k/2, k);k /= 2;}
}

由上至下的堆有序化(下沉)

如果堆有序状态因为某个结点变得比它的两个子节点或是其中之一更小而被打破了,那么我们可以通过将它和它的两个子节点中的较大者交换来恢复堆。交换可能会在子节点处继续打破堆的有序状态,因此我们需要不断地用相同的方式将其修复,将节点下移直到它的子节点都比它更小或者到达了堆的底部。

private void sink(int k) {while (2 * k <= N) {int j = 2 * k;if (j < n && less(j, j + 1)) ++j;if (!less(k, j)) break;exch(k, j);k = j;}
}

插入和删除元素

插入新元素:我们将新元素添加到数组末尾,增加堆的大小并让这个新元素上浮到合适的位置。
删除最大元素:我们将数组顶端删去最大的元素并将数组的最后一个元素放到顶端,减小堆的大小并让这个元素下沉到合适的位置。

具体实现

public class MaxPQ <Key extends Comparable<Key>> {private Key[] pq;private int N = 0;public MaxPQ(int maxN) {pq = (Key[]) new Comparable[maxN + 1];}public boolean isEmpty() {return N == 0;}public int size() {return N;}public void insert(Key v) {pq[++N] = v;swim(N);}public Key delMax() {Key max = pq[1];exch(1, N--);pq[N + 1] = null;sink(1);return max;}private boolean less(int i, int j)private void exch(int i, int j)private void swim(int k)private void sink(int k)
}

对于一个含有N个元素的基于堆的优先队列,插入元素操作只需不超过(logN + 1)次比较,删除最大元素的操作需要不超过2logN次比较

相关文章:

【数据结构】优先队列

优先队列 API初级实现使用堆实现由下至上的堆有序化&#xff08;上浮&#xff09;由上至下的堆有序化&#xff08;下沉&#xff09;插入和删除元素具体实现 很多情况下我们需要有序的处理输入的元素&#xff0c;但是又不需要输入的元素全部有序&#xff0c;或者不需要一次将它们…...

如何在 Ubuntu 22.04 下编译 StoneDB for MySQL 8.0 | StoneDB 使用教程 #1

作者&#xff1a;双飞&#xff08;花名&#xff1a;小鱼&#xff09; 杭州电子科技大学在读硕士 StoneDB 内核研发实习生 ❝ 大家好&#xff0c;我是 StoneDB 的实习生小鱼&#xff0c;目前正在做 StoneDB 8.0 内核升级相关的一些事情。刚开始接触数据库开发没多久&#xff0c…...

AMEYA360:尼得科科宝旋转型DIP开关系列汇总

旋转型DIP开关 S-4000 电路&#xff1a;BCD(十进制) 代码格式&#xff1a;实码 安装类型&#xff1a;表面贴装 调整位置&#xff1a;顶部 可水洗&#xff1a;无 端子类型&#xff1a;J 引线, 鸥翼型 旋转型DIP开关 SA-7000 电路&#xff1a;BCD(十进制), BCH(十六进制) 代码格式…...

为什么感觉 C/C++ 不火了?

首先C和C是两个非常不一样的编程语言。 C语言在系统开发领域地位非常稳固&#xff0c;几乎没有替代产品。应用层开发近年来略微有被Rust取代的迹象。 C由于支持的编程范式过多&#xff0c;导致不同水平的人写出来的代码质量差异太大&#xff0c;这给软件的稳健性带来了很大的…...

【Linux】在服务器上创建Crontab(定时任务),自动执行shell脚本

业务场景&#xff1a;该文即为上次编写shell脚本的姊妹篇,在上文基础上,将可执行的脚本通过linux的定时任务自动执行,节省人力物力,话不多说,开始操作! 一、打开我们的服务器连接工具 连上服务器后,在任意位置都可以执行:crontab -e 如果没有进入编辑cron任务模式 根据提示查看…...

内存分析工具之Mat

自定义类MatClazz内存个数为9521。当前对象占用内存为16个字节。不包括其属性bytes的字节数。 通过查看MatClazz引用的类之byte数组之bytes。其单个数组占用的字节数为10256。整个内存MatClazz中属性bytes占用的byte[]字节数为97746376&#xff0c;与直方图统计趋近。 通过选…...

【逗老师的PMP学习笔记】项目的运行环境

一、影响项目运行的因素 主要分两种因素 事业环境因素&#xff08;更多的是制约和限制因素&#xff09;组织过程资产&#xff08;可以借鉴的经验和知识&#xff09; 1、细说事业环境因素&#xff08;更多的是制约和限制因素&#xff09; 资源可用性 例如包括合同和采购制约…...

Rust- 模块

&#xff08;1&#xff09;在项目根目录下创建mylib&#xff08;里面实现自定义的外部模块&#xff09; cargo new --lib mylib &#xff08;2&#xff09;在 项目名\mylib\src\lib.rs文件中实现新模块 pub mod add_salary {pub fn study(name: String) {println!("Rust…...

【开源源码学习】

C 迷你高尔夫 一款打高尔夫的游戏。亮点是碰撞反应和关卡设计。 GitHub - mgerdes/Open-Golf: A cross-platform minigolf game written in C. TypeScript 俄罗斯方块 复刻经典的俄罗斯方块&#xff0c;项目采用ReactReduxImmutable的技术栈。 GitHub - chvin/react-tetr…...

CNN-NER论文详解

论文&#xff1a;https://arxiv.org/abs/2208.04534 代码&#xff1a;https://github.com/yhcc/CNN_Nested_NER/tree/master 文章目录 有关工作前期介绍CNN-NER模型介绍 代码讲解主类多头biaffineCNNLoss解码数据传入格式 参考资料 有关工作 前期介绍 过去一共主要有四类方式…...

利用ChatGPT制作行业应用:哪些行业最受益

引言 随着人工智能技术的快速发展&#xff0c;ChatGPT&#xff08;Chat Generative Pre-trained Transformer&#xff09;成为了一种引人注目的工具&#xff0c;它能够生成自然流畅的对话内容。这种技术不仅在娱乐领域有着广泛的应用&#xff0c;还可以在各个行业中发挥重要作…...

【SA8295P 源码分析】60 - QNX Host 如何新增 android_test 分区给 Android GVM 挂载使用

【SA8295P 源码分析】60 - QNX Host 如何新增 android_test 分区给 Android GVM 挂载使用 一、QNX 侧:创建分区、配置下载、配置透传1.1 修改分区表,新增 android_test 分区,大小为 2GByte1.2 配置下载 android_test.img 镜像1.3 配置 /dev/disk/android_test_a 分区透传到 …...

Linux 用户和权限

一、root 用户 root 用户(超级管理员) 无论是windows、Macos、Linux均采用多用户的管理模式进行权限管理。在Linux系统中&#xff0c;拥有最大权限的账户名为&#xff1a;root (超级管理员)。 root用户拥有最大的系统操作权限&#xff0c;而普通用户在许多地方的权限是受限的。…...

分布式应用:ELFK集群部署

目录 一、理论 1.ELFK集群 2.filebeat 3.部署ELK集群 二、实验 1. ELFK集群部署 三、总结 一、理论 1.ELFK集群 &#xff08;1&#xff09;概念 ELFK集群部署&#xff08;FilebeatELK&#xff09;&#xff0c;ELFK ES logstashfilebeatkibana 。 数据流 架构 2.fi…...

Quartz使用文档,使用Quartz实现动态任务,Spring集成Quartz,Quartz集群部署,Quartz源码分析

文章目录 一、Quartz 基本介绍二、Quartz Java 编程1、文档2、引入依赖3、入门案例4、默认配置文件 三、Quartz 重要组件1、Quartz架构体系2、JobDetail3、Trigger&#xff08;1&#xff09;代码实例&#xff08;2&#xff09;SimpleTrigger&#xff08;3&#xff09;CalendarI…...

Go -- 测试 and 项目实战

没有后端基础&#xff0c;学起来真是费劲&#xff0c;所以打算速刷一下&#xff0c;代码跟着敲一遍&#xff0c;有个印象&#xff0c;大项目肯定也做不了了&#xff0c;先把该学的学了&#xff0c;有空就跟点单体项目&#xff0c;还有该看的书.... 目录 &#x1f34c;单元测试…...

GitHub基本使用

GitHub搜索 直接搜索 直接搜索关键字 明确搜索仓库标题 语法&#xff1a;in:name [关键词]展示&#xff1a;比如我们想在GitHub仓库中标题中搜索带有SpringBoot关键词的&#xff0c;我们可以样搜: in:name SpringBoot 明确搜索描述 语法&#xff1a;in:description [关键词]展…...

微信小程序生成带参数的二维码base64转png显示

getQRCode() {var that this;wx.request({url: http://localhost:8080/getQRCode?ID 13,header: {content-type: application/json},method: POST,responseType: arraybuffer,//将原本按文本解析修改为arraybuffersuccess(res) {that.setData({getQRCode: wx.arrayBufferToB…...

量子计算机:下一代计算技术的奇点

介绍 量子计算机是一种基于量子力学原理的全新计算技术&#xff0c;它利用量子比特的特性进行计算&#xff0c;具有破解当前经典计算机难以解决问题的潜力。在过去几十年里&#xff0c;量子计算机一直是计算机科学领域的一个热门话题。本篇博客将深入探讨量子计算机的基本原理…...

【ChatGPT】ChatGPT是如何训练得到的?

前言 ChatGPT是一种基于语言模型的聊天机器人&#xff0c;它使用了GPT&#xff08;Generative Pre-trained Transformer&#xff09;的深度学习架构来生成与用户的对话。GPT是一种使用Transformer编码器和解码器的预训练模型&#xff0c;它已被广泛用于生成自然语言文本的各种…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...