当前位置: 首页 > 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;它已被广泛用于生成自然语言文本的各种…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...