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

优先队列PriorityQueue源码解析

基本信息

实现了队列接口:Queue --> AbstractQueue --> PriorityQueue

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {public abstract class AbstractQueue<E> extends AbstractCollection<E>implements Queue<E> {

底层 逻辑 数据结构: 堆
底层 物理 数据结构:数组

    // 默认数组长度11private static final int DEFAULT_INITIAL_CAPACITY = 11;// transient: JVM在对象序列化时忽略指定变量,从而避免数据泄露的安全问题transient Object[] queue; private int size = 0;// 定义的比较器,否则用元素的默认顺序private final Comparator<? super E> comparator;

元素不能为null,看下面initElementsFromCollection函数、及offer函数

关键函数

添加元素

public boolean add(E e) {// 直接调用offerreturn offer(e);}public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;// 长度不够扩充容量int i = size;if (i >= queue.length)grow(i + 1);size = i + 1;if (i == 0)queue[0] = e;else// 把e放在了末尾i位置,故要进行 上滤 操作siftUp(i, e);return true;}

弹出元素

public E poll() {if (size == 0)return null;int s = --size;modCount++;// 默认第0个元素就是要弹出的元素E result = (E) queue[0];E x = (E) queue[s];queue[s] = null;if (s != 0)siftDown(0, x);return result;}

peek函数

// 返回头部元素,并不会删除元素
public E peek() {return (size == 0) ? null : (E) queue[0];}

从集合初始化

public PriorityQueue(Collection<? extends E> c) {if (c instanceof SortedSet<?>) {SortedSet<? extends E> ss = (SortedSet<? extends E>) c;this.comparator = (Comparator<? super E>) ss.comparator();initElementsFromCollection(ss);}else if (c instanceof PriorityQueue<?>) {PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;this.comparator = (Comparator<? super E>) pq.comparator();initFromPriorityQueue(pq);}else {// 通常情况下,从集合初始化,则不能指定comparatorthis.comparator = null;initFromCollection(c);}}private void initFromCollection(Collection<? extends E> c) {// 从集合初始化数组、sizeinitElementsFromCollection(c);// 构建堆heapify();}
private void initElementsFromCollection(Collection<? extends E> c) {Object[] a = c.toArray();......int len = a.length;// 元素不能为nullif (len == 1 || this.comparator != null)for (int i = 0; i < len; i++)if (a[i] == null)throw new NullPointerException();this.queue = a;this.size = a.length;}private void heapify() {// 对数组 构建 堆for (int i = (size >>> 1) - 1; i >= 0; i--)siftDown(i, (E) queue[i]);}

上移、下降

下降

private void siftDown(int k, E x) {if (comparator != null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x);}private void siftDownUsingComparator(int k, E x) {int half = size >>> 1;// half还是叶子结点,若k=half,则k为叶子结点,无法向下了while (k < half) {// 左子树int child = (k << 1) + 1;Object c = queue[child];int right = child + 1;// 取 左右子树 最小值(优先右子树)if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0)c = queue[child = right];// x的值比左右子树 值 小,则当前位置就是目标位置if (comparator.compare(x, (E) c) <= 0)break;queue[k] = c;k = child;}// x从i位置下降到了k位置queue[k] = x;}

上移

private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}private void siftUpUsingComparator(int k, E x) {// 0位置无法上升了while (k > 0) {// 父节点位置:(k-1)/2int parent = (k - 1) >>> 1;Object e = queue[parent];// x比父节点小,则上移,否则,找到目标位置if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}// 目标位置放置xqueue[k] = x;}

相关文章:

优先队列PriorityQueue源码解析

基本信息 实现了队列接口&#xff1a;Queue --> AbstractQueue --> PriorityQueue public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {public abstract class AbstractQueue<E> extends AbstractCollection…...

前端开发中常见的跨域问题及解决方案

引言 在前端开发中&#xff0c;跨域问题是一个非常常见的问题。本文将详细介绍什么是跨域&#xff0c;常见的跨域场景&#xff0c;以及各种常用的跨域解决方案。 什么是跨域 跨域是指一个网页或者Web应用在浏览器中发起对另一个域名下资源的请求。由于浏览器的同源策略限制&…...

(超详解)堆排序+(图解)

目录&#xff1a; 1:如何建堆(两种方法) 2:两种方法建堆的时间复杂度分析与计算 3:不同类型的排序方式我们应该如何建堆 文章正式开始&#xff1a; 1&#xff1a;如何建堆 在实现堆排序之前我们必须得建堆&#xff0c;才能够实现堆排序 首先在讲解如何建堆之前让我们先来回顾一…...

Hadoop的YARN高可用

一、YARN简介 Hadoop2.0即第二代Hadoop&#xff0c;由分布式存储系统HDFS、并行计算框架MapReduce和分布式资源管理系统YARN三个系统组成&#xff0c;其中YARN是一个资源管理系统&#xff0c;负责集群资源管理和调度&#xff0c;MapReduce则是运行在YARN上的离线处理框架。 Y…...

C++内存检查

内存泄漏是程序中常见&#xff0c;也是最令人痛苦的一种bug。好在有一些检查工具可以帮助我们&#xff0c;这里介绍一个google 提供的简单直接的工具 Address-Sanitizer (ASAN)。 预备条件 ASAN 原来是LLVM 中的特性&#xff0c;后来GCC 4.8中也开始支持。也就是说&#xff0…...

防火墙概述及实战

目录 前言 一、概述 &#xff08;一&#xff09;、防火墙分类 &#xff08;二&#xff09;、防火墙性能 &#xff08;三&#xff09;、iptables &#xff08;四&#xff09;、iptables中表的概念 二、iptables规则匹配条件分类 &#xff08;一&#xff09;、基本匹配条…...

nginx代理故障总结

一、故障现象 今天公司的某个系统文件下载功能失败&#xff0c;报错network error&#xff0c;其他功能正常。 二、故障定位 首先我们检查了公司的网络情况&#xff0c;包括网络路由、防火墙策略、终端安全产品等&#xff0c;均未发现异常。 尝试访问http://X.X.X.X:7002端口&…...

python爬虫爬取电影数据并做可视化

思路&#xff1a; 1、发送请求&#xff0c;解析html里面的数据 2、保存到csv文件 3、数据处理 4、数据可视化 需要用到的库&#xff1a; import requests,csv #请求库和保存库 import pandas as pd #读取csv文件以及操作数据 from lxml import etree #解析html库 from …...

哈希及哈希表的实现

目录 一、哈希的引入 二、概念 三、哈希冲突 四、哈希函数 常见的哈希函数 1、直接定址法 2、除留余数法 五、哈希冲突的解决 1、闭散列 2、开散列 一、哈希的引入 顺序结构以及平衡树中&#xff0c;元素关键码与其存储位置之间没有对应的关系&#xff0c;因此在查找…...

CLIP 基础模型:从自然语言监督中学习可转移的视觉模型

一、说明 在本文中&#xff0c;我们将介绍CLIP背后的论文&#xff08;Contrastive Language-I mage Pre-Training&#xff09;。我们将提取关键概念并分解它们以使其易于理解。此外&#xff0c;还对图像和数据图表进行了注释以澄清疑问。 图片来源&#xff1a; 论文&#xff1a…...

解读性能指标TP50、TP90、TP99、TP999

TP指标说明 TP指标: 指在一个时间段内&#xff0c;统计该方法每次调用所消耗的时间&#xff0c;并将这些时间按从小到大的顺序进行排序, 并取出结果为&#xff1a;总次数*指标数对应TP指标的值&#xff0c;再取出排序好的时间。 TPTop Percentile&#xff0c;Top百分数&#…...

【无标题】mysql 截取两个,之间字符串

截取两个&#xff0c;之间字符串 select area,SUBSTRING_INDEX(et.area,,,1) as XZQH1,if(length(et.area)-length(replace(et.area,,,))>1,SUBSTRING_INDEX(SUBSTRING_INDEX(et.area,,,2),,,-1),NULL) AS XZQH2,if(length(et.area)-length(replace(et.area,,,))>2,SUBS…...

全局的键盘监听事件

一、设定全局键盘监听事件 放在vue 的created()或者mounted ()中&#xff0c;可对整个文档进行键盘事件监听。 new Vue({ created() { window.addEventListener(keydown, this.handleKeydown); }, beforeDestroy() { window.removeEventListener(keydown, this.handleK…...

Qt自定义QSlider(支持水平垂直)

实现背景&#xff1a; Qt本身有自己的QSlider&#xff0c;为什么我们还要自定义实现呢&#xff0c;因为Qt自带的QSlider存在一个问题&#xff0c;当首尾为圆角时&#xff0c;滑动滚动条到首尾时会出现圆角变成矩形的问题。当然如果QSS之间的margin和滑动条的圆角控制的好的话是…...

会话控制学习

文章目录 介绍cookieexpress中使用cookie获取cookie session配置区别 介绍 cookie express中使用cookie 退出登录就是删除cookie 获取cookie 添加中间键后&#xff0c;直接获取 session 配置 区别...

dweb-browser阅读

dweb-browser阅读 核心模块js.browser.dwebjmm.browser.dwebmwebview.browser.dwebnativeui.browser.dweb.sys.dweb plaoc插件 核心模块 js.browser.dweb 它是一个 javascript-runtime&#xff0c;使用的是 WebWorker 作为底层实现。它可以让您在 dweb-browser 中运行 javasc…...

ChatGPT:使用fastjson读取JSON数据问题——如何使用com.alibaba.fastjson库读取JSON数据的特定字段

ChatGPT&#xff1a;使用fastjson读取JSON数据问题——如何使用com.alibaba.fastjson库读取JSON数据的特定字段 有一段Json字符串&#xff1a; {"code": 200,"message": "success","data": {"total": "1","l…...

2、ARM处理器概论

一、ARM处理器概述 1、ARM的含义 ARM&#xff08;Advanced RISC Machines&#xff09;有三种含义&#xff0c;一个公司的名称、一类处理器的通称、一种技术 ARM公司&#xff1a; 成立于1990年11月&#xff0c;前身为Acorn计算机公司主要设计ARM系列RISC处理器内核授权ARM内…...

【Python】福利彩票复式模拟选号程序

【效果】 【注意】 逻辑是用Random模拟10000次复试彩票选号,然后给出最大可能性一组。但是模拟终究是模拟,和现实彩票结果没有任何联系,下载下来玩就是了,没人能保证模拟出中奖号码,不要投机,不要投机! 【修改】 代码很简单,如果想改成不是复式的,自行修改即可。 如…...

Pytorch 机器学习专业基础知识+神经网络搭建相关知识

文章目录 一、三种学习方式二、机器学习的一些专业术语三、模型相关知识四、常用的保留策略五、数据处理六、解决过拟合与欠拟合七、成功的衡量标准 一、三种学习方式 有监督学习&#xff1a; 1、分类问题 2、回归问题 3、图像分割 4、语音识别 5、语言翻译 无监督学习 1、聚类…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

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

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

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...