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

【Collection - PriorityQueue源码解析】

本文主要对Collection - PriorityQueue进行源码解析。

  • Collection - PriorityQueue源码解析
    • 概述
    • 方法剖析
      • add()和offer()
      • element()和peek()
      • remove()和poll()
      • remove(Object o)

 概述

前面以Java ArrayDeque为例讲解了StackQueue,其实还有一种特殊的队列叫做PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素,C++的优先队列每次取最大元素)。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator,类似于C++的仿函数)。

Java中PriorityQueue实现了Queue接口,不允许放入null元素;其通过堆实现,具体说是通过完全二叉树(complete binary tree)实现的小顶堆(任意一个非叶子节点的权值,都不大于其左右子节点的权值),也就意味着可以通过数组来作为PriorityQueue的底层实现。

给每个元素按照层序遍历的方式进行了编号,父节点和子节点的编号是有联系的,更确切的说父子节点的编号之间有如下关系:

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

通过上述三个公式,可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。

PriorityQueuepeek()element操作是常数时间,add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)

 方法剖析

 add()和offer()

add(E e)offer(E e)的语义相同,都是向优先队列中插入元素,只是Queue接口规定二者对插入失败时的处理不同,前者在插入失败时抛出异常,后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。

新加入的元素可能会破坏小顶堆的性质,因此需要进行必要的调整。

//offer(E e)
public boolean offer(E e) {if (e == null)//不允许放入null元素throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);//自动扩容size = i + 1;if (i == 0)//队列原来为空,这是插入的第一个元素queue[0] = e;elsesiftUp(i, e);//调整return true;
}

上述代码中,扩容函数grow()类似于ArrayList里的grow()函数,就是再申请一个更大的数组,并将原数组的元素复制过去,这里不再赘述。需要注意的是siftUp(int k, E x)方法,该方法用于插入元素x并维持堆的特性。

//siftUp()
private void siftUp(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法break;queue[k] = e;k = parent;}queue[k] = x;
}

新加入的元素x可能会破坏小顶堆的性质,因此需要进行调整。调整的过程为** : 从k指定的位置开始,将x逐层与当前点的parent进行比较并交换,直到满足x >= queue[parent]为止**。注意这里的比较可以是元素的自然顺序,也可以是依靠比较器的顺序。

 element()和peek()

element()peek()的语义完全相同,都是获取但不删除队首元素,也就是队列中权值最小的那个元素,二者唯一的区别是当方法失败时前者抛出异常,后者返回null。根据小顶堆的性质,堆顶那个元素就是全局最小的那个;由于堆用数组表示,根据下标关系,0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可

代码也就非常简洁:

//peek()
public E peek() {if (size == 0)return null;return (E) queue[0];//0下标处的那个元素就是最小的那个
}

 remove()和poll()

remove()poll()方法的语义也完全相同,都是获取并删除队首元素,区别是当方法失败时前者抛出异常,后者返回null。由于删除操作会改变队列的结构,为维护小顶堆的性质,需要进行必要的调整。

代码如下:

public E poll() {if (size == 0)return null;int s = --size;modCount++;E result = (E) queue[0];//0下标处的那个元素就是最小的那个E x = (E) queue[s];queue[s] = null;if (s != 0)siftDown(0, x);//调整return result;
}

上述代码首先记录0下标处的元素,并用最后一个元素替换0下标位置的元素,之后调用siftDown()方法对堆进行调整,最后返回原来0下标处的那个元素(也就是最小的那个元素)。重点是siftDown(int k, E x)方法,该方法的作用是k指定的位置开始,将x逐层向下与当前点的左右孩子中较小的那个交换,直到x小于或等于左右孩子中的任何一个为止

//siftDown()
private void siftDown(int k, E x) {int half = size >>> 1;while (k < half) {//首先找到左右孩子中较小的那个,记录到c里,并用child记录其下标int child = (k << 1) + 1;//leftNo = parentNo*2+1Object c = queue[child];int right = child + 1;if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0)c = queue[child = right];if (comparator.compare(x, (E) c) <= 0)break;queue[k] = c;//然后用c取代原来的值k = child;}queue[k] = x;
}

 remove(Object o)

remove(Object o)方法用于删除队列中跟o相等的某一个元素(如果有多个相等,只删除一个),该方法不是Queue接口内的方法,而是Collection接口的方法。由于删除操作会改变队列结构,所以要进行调整;又由于删除元素的位置可能是任意的,所以调整过程比其它函数稍加繁琐。具体来说,remove(Object o)可以分为2种情况: 1. 删除的是最后一个元素。直接删除即可,不需要调整。2. 删除的不是最后一个元素,从删除点开始以最后一个元素为参照调用一次siftDown()即可。此处不再赘述。

具体代码如下:

//remove(Object o)
public boolean remove(Object o) {//通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标int i = indexOf(o);if (i == -1)return false;int s = --size;if (s == i) //情况1queue[i] = null;else {E moved = (E) queue[s];queue[s] = null;siftDown(i, moved);//情况2......}return true;
}


相关文章:

【Collection - PriorityQueue源码解析】

本文主要对Collection - PriorityQueue进行源码解析。 Collection - PriorityQueue源码解析 概述方法剖析 add()和offer()element()和peek()remove()和poll()remove(Object o) 概述 前面以Java ArrayDeque为例讲解了Stack和Queue&#xff0c;其实还有一种特殊的队列叫做Priori…...

Javascript_根据截止日期超时自动返回

例如定时交卷功能&#xff0c;隐藏一个input id"endTime"存放超时时间&#xff0c;例如2023-12-01 20:56:15&#xff0c;使用如下代码即可实现超时自动处理。 <script src"/jquery.min.js"></script><script type"text/javascript&qu…...

记录 | vscode设置自动换行

右上菜单栏 -> 查看 -> 打开自动换行 或者还有种方式&#xff0c;如下&#xff0c; 左下角小齿轮&#xff0c;点击设置 然后输入 Editor: Word Wrap &#xff0c;把开关打开为 on...

k8s引用环境变量

一 定义环境变量 ① 如何在k8s中定义环境变量 env、configmap、secret补充&#xff1a; k8s 创建Service自带的环境变量 ② 从pod属性中获取 kubectl explain deploy.spec.template.spec.containers.env.valueFrom关注&#xff1a; configMapKeyRef、fieldRef 和 resour…...

navicate16 2059 plugin http could not be loaded

plugin http could not be loaded 乱码 library path http.dll 今天新装一台机子的navicate遇到这个问题。 查了半天都是说 caching_sha2_password’的解决办法。 然后是咋解决的呢&#xff0c;真是丢脸 由于我是直接从浏览器复制下来的ip&#xff0c;所以虽然我只复制了ip地…...

dp-基础版动态规划(动态规划每日一题计划)10/50

最小路径和 class Solution {public static int minPathSum(int[][] grid) {int dp[][]new int[grid.length][grid[0].length];dp[0][0]grid[0][0];for(int i1;i<grid[0].length;i){dp[0][i]grid[0][i]dp[0][i-1];}for(int i1;i<grid.length;i){dp[i][0]grid[i][0]dp[i-…...

轻食沙拉店外卖配送小程序商城效果如何

轻食沙拉店也是餐饮业中较为受欢迎的品类&#xff0c;其具备健康属性绿色食材涵盖广泛人群&#xff0c;虽然如此&#xff0c;但也缺乏一定市场教育&#xff0c;部分消费者依然对这一类目知之甚少&#xff0c;而商家想要进一步扩大生意&#xff0c;就需要不断品牌宣传、餐品销售…...

Oracle ADRCI工具使用说明

1.ADRCI介绍 ADRCI是一个命令行工具&#xff0c;是Oracle 11g中引入的故障可诊断性架构的一部分。 ADRCI可以完成以下&#xff1a; 查看自动诊断信息库&#xff08;ADR&#xff09;中的诊断数据。 查看Health Monitor报告。 将事件和问题信息打包到zip文件中以传输到Oracle Su…...

Amazon CodeWhisperer 正式可用, 并面向个人开发者免费开放

文章作者&#xff1a;深度-围观 北京——2023年4月18日&#xff0c;亚马逊云科技宣布&#xff0c;实时 AI 编程助手 Amazon CodeWhisperer 正式可用&#xff0c;同时推出的还有供所有开发人员免费使用的个人版&#xff08;CodeWhisperer Individual&#xff09;。CodeWhisperer…...

8-Hive原理与技术

单选题 题目1&#xff1a;按粒度大小的顺序&#xff0c;Hive数据被分为&#xff1a;数据库、数据表、桶和什么 选项: A 元祖 B 栏 C 分区 D 行 答案&#xff1a;C ------------------------------ 题目2&#xff1a;以下选项中&#xff0c;哪种类型间的转换是被Hive查询语言…...

cloudflare Tunnel完整

下载和安装 curl -L ‘https://github.com/cloudflare/cloudflared/releases/latest/download/cloudflared-linux-amd64’ -o ./cloudflared-linux-amd64 280 chmod x ./cloudflared-linux-amd64 281 ./cloudflared-linux-amd64 282 mv cloudflared-linux-amd64 cloudflared …...

微信聊天窗口测试用例

以前没测过客户端的测试&#xff0c;昨天面试被问到聊天窗口测试场景设计&#xff0c;感觉自己答的不好&#xff0c;结束后上网查了一下客户端/app测试的要点&#xff0c;按照测试策略来分&#xff0c;主要涉及到如下测试类型&#xff1a; 1、功能测试 2、性能测试 3、界面测试…...

Linux下配置邮箱客户端MUTT,整合msmtp + procmail + fetchmail

一、背景 在向 Linux kernel 社区提交patch补丁步骤总结&#xff08;已验证成功&#xff09;_kernel补丁-CSDN博客文章中提到如何向kernel社区以及其他类似如qemu、libvirt社区提交patch的详细步骤&#xff0c;但还有一点不足的是通过git send-email这种方法基本是只能发送patc…...

[每周一更]-(第75期):Go相关粗浅的防破解方案

Go作为编译语言&#xff0c;天然存在跨平台的属性&#xff0c;我们在编译完成后&#xff0c;可以再不暴露源代码的情况下&#xff0c;运行在对应的平台中&#xff0c;但是 还是架不住有逆向工程师的反编译、反汇编的情形&#xff1b;&#xff08;当然我们写的都不希望被别人偷了…...

停留时间是您需要跟踪的 SEO 指标

介绍 停留时间是指用户在点击搜索引擎结果后但在返回搜索引擎结果页面之前在网站上花费的时间。它是搜索引擎优化 &#xff08;SEO&#xff09; 的一个重要指标&#xff0c;因为它衡量用户参与度并指示网站是否向访问者提供有价值且相关的内容。搜索引擎&#xff0c;如谷歌&am…...

ES常用操作语句

ES常用操作语句 注&#xff1a;本文中的操作语句基于ES5.5和7.7的版本&#xff0c;版本不同操作语句上可能有细微差别&#xff0c;如5.5版本有索引类型&#xff0c;7.7版本已废弃&#xff0c;查询不应该带索引类型 新增 # 添加字段&#xff0c;并设置字段类型 PUT /索引/_map…...

MicroPython STM32F4 RTC功能使用介绍

MicroPython STM32F4 RTC功能使用介绍 &#x1f516;STM32和ESP32 RTC功能差不多&#xff0c;相关篇《MicroPython ESP32 RTC功能使用介绍》&#x1f4cc;固件刷可参考前面一篇《STM32刷Micropython固件参考指南》&#x1f33f; 相关篇《Micropython STM32F4入门点灯》&#x1…...

【鸿蒙应用ArkTS开发系列】- 选择图片、文件和拍照功能实现

文章目录 前言创建多媒体Demo工程创建MediaBean 实体类创建MediaHelper工具类API标记弃用问题动态申请多媒体访问权限实现选择图片显示功能打包测试 前言 在使用App的时候&#xff0c;我们经常会在一些社交软件中聊天时发一些图片或者文件之类的多媒体文件&#xff0c;那在鸿蒙…...

公有云迁移研究——AWS Route53

大纲 1 什么是Route 532 Route 53能做些什么# 3 通过DNS托管来实现分流3.1 创建DNS托管3.2 对托管创建记录对流量进行分配 4 通过流量策略来对流量进行分流4.1 创建流量策略 5 对比两者的区别6 推荐 在给客户从本地机房往AWS迁移的过程中&#xff0c;我们接到如下需求&#xff…...

浪潮信息KeyarchOS——保卫数字未来的安全防御利器

浪潮信息KeyarchOS——保卫数字未来的安全防御利器 前言 众所周知&#xff0c;目前流行的操作系统有10余种&#xff0c;每一款操作系统都有自己的特点。作为使用者&#xff0c;我们该如何选择操作系统。如果你偏重操作系统的安全可信和稳定高效&#xff0c;我推荐你使用浪潮信…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...