数据结构——优先级队列(堆)Priority Queue详解

1. 优先级队列

队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列,该场景下,使用队列不合适

在这种情况下,数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象,这种数据结构就是优先级队列(Priority Queue)

2. 优先级队列的模拟实现

2.1 堆的概念

性质:

如上图,堆中某个节点的值总是不大于其父节点的值,称为最小堆/小根堆

堆中某个节点的值总是不小于其父节点的值,称为最大堆/大根堆

堆总是一棵完全二叉树

2.2 堆的存储方式

从堆的概念可知,堆是一棵完全二叉树,因此可用层序的规则采用顺序的方式进行高效存储

tip:对于非完全二叉树则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节点,就会导致空间利用率较低

将元素存储到数组中后,假设 i 为节点在数组中的下标,则有:

  • 如果 i 为0,则 i 表示的节点为根节点,否则 i 节点的双亲结点为(i - 1)/2
  • 如果 2*i+1 小于节点个数,则节点 i 的左孩子下标为 2*i+1 ,否则没有左孩子
  • 如果 2*i+2 小于节点个数,则节点 i 的右孩子下标为 2*i+2 ,否则没有右孩子

2.3 堆的创建

2.3.1 堆向下调整

以集合{ 27,15,19,18,28,34,65,49,25,37 }为例,转换为大根堆的过程:

//TestHeap 类
public class TestHeap {public int[] elem;//堆由数组实现public int usedSize;//记录有效数据个数public TestHeap() {//构造方法this.elem = new int[10];}public void init(int[] array) {//给数组初始化for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}//把elem数组中的数据调整为大根堆public void createHeap() {//让parent初始位置在树的最后一棵子树的根节点处,用到公式:根节点 = (i-1)/2//其中usedSize-1表示最后一个节点,从上到下循环遍历整棵树for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {//siftDown方法用来判断树中左右孩子与父亲节点的大小关系siftDown(parent,usedSize);}}//交换函数public void swap(int i, int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}public void siftDown(int parent, int end) {int child = 2*parent+1;//公式:左孩子下标 = 2*根节点下标+1while(child < end) {//end是有效数据个数,不能用<=//下面if走完之后,child一定是左右孩子中最大值的下标if(child+1 < end && elem[child] < elem[child+1]) {child++;}//下面if判断孩子节点是否大于父亲节点,若大于则交换,否则跳出循环,去判断上一棵树if(elem[child] > parent) {swap(child,parent);parent = child;child = 2*parent+1;}else {break;}}}
}//Test 类
public class Test {public static void main(String[] args) {int[] array = {27,15,19,18,28,34,65,49,25,37};TestHeap testHeap = new TestHeap();testHeap.init(array);testHeap.createHeap();}
}

tip:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆,才可以向下调整

时间复杂度:最坏的情况就如上例,从根一路比较到叶子,比较的次数为完全二叉树的高度,即时间复杂度为O(\log _{2}N)

2.3.2 建堆的时间复杂度

推导:

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了方便计算,使用满二叉树来推导

结论: 建堆的时间复杂度为 O(N)

2.4 堆的插入与删除

2.4.1 堆的插入

堆的插入需要两步

1. 先将元素放到树底层最后一个节点(空间不够时扩容)

2. 将插入新节点向上调整,直到满足堆的性质

    public void offer(int val) {if(isFull()) {//判满,若满则扩容elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;//val赋值到usedSize位置,usedSize++usedSize++;siftUp(usedSize-1);//向上调整}public void siftUp(int child) {int parent = (child-1)/2;//通过孩子节点找到父亲节点while(parent >= 0) {//当父亲节点下标小于0,说明向上调整结束了,堆已有序if(elem[child] > elem[parent]) {//孩子节点的值大于父亲节点值,即交换swap(child,parent);child = parent;parent = (child-1)/2;}else {//若孩子节点的值小于父亲节点的值,说明堆已有序,直接跳出循环break;}}}public boolean isFull() {return usedSize == elem.length;}

2.4.2 堆的删除

tip:堆的删除一定删除的是堆顶元素,分为三步:

1. 将堆定元素对堆中最后一个元素交换

2. 将堆中有效数据个数减少一个

3. 对堆顶元素进行向下调整

    public int poll() {if(isEmpty()) {//若栈空,返回-1return -1;}int old = elem[0];//记录要删除的数据,最后返回swap(0,usedSize-1);//交换堆顶元素和最后元素usedSize--;//有效个数--siftDown(0,usedSize);//从堆定开始,向下调整return old;}public boolean isEmpty() {return usedSize == 0;}

例题:

1.下列关键字序列为堆的是:()

A: 100,60,70,50,32,65   B: 60,70,65,50,32,100   C: 65,100,70,32,50,60

D: 70,65,100,32,50,60   E: 32,50,100,70,65,60   F: 50,100,70,65,60,32

选A

2.已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,在此过程中,关键字之间的比较次数是()

A: 1         B: 2          C: 3        D: 4

解析:选C,15与10比,12与10比,12与16比

3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后,其结果是()

A: [3,2,5,7,4,6,8]        B: [2,3,5,7,4,6,8]

C: [2,3,4,5,7,8,6]        D: [2,3,4,5,6,7,8]

选C

3. 常用接口介绍

3.1 PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,本文主要介绍PriorityQueue

    public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);System.out.println(priorityQueue.poll());//运行结果:1System.out.println(priorityQueue.poll());//        2}

关于PriorityQueue的使用注意:

  • 1.使用时必须导入PriorityQueue所在的包,即:import java.util.PriorityQueue;
  • 2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException 异常 
  • 3. 不能插入null对象,否则会抛出 NullPointerException
  • 4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容
  • 5. 插入和删除元素的时间复杂度为O(log_2N)
  • 6. PriorityQueue底层使用了堆数据结构
  • 7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

3.2 PriorityQueue常用接口介绍

3.2.1 优先级队列的构造

此处只是常见的几种:

构造器功能介绍
PriorityQueue()创建一个空的优先级队列,默认容量是11
PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列,注意: initialCapacity不能小于1,否则会抛IllegalArgumentException异 常
PriorityQueue(Collection c)用一个集合来创建优先级队列

构造方法原理:

用一个集合来创建优先级队列:

class Student {}
public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arrayList);priorityQueue.offer(4);priorityQueue.offer(5);priorityQueue.offer(6);System.out.println(priorityQueue.poll());//运行结果:1System.out.println(priorityQueue.poll());//        2PriorityQueue<Student> priorityQueue1 = new PriorityQueue<>(arrayList);//error//传入参数必须是Student类或其子类}
}

3.2.2 offer元素原理:

查看源码:

结合上面创建小根堆的流程分析:

自己实现比较器:

//实现小根堆的比较器
class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o1.compareTo(o2);//小根堆}
}
public class Test {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());//别忘了此处new比较器对象作为参数priorityQueue.offer(4);priorityQueue.offer(5);priorityQueue.offer(6);System.out.println(priorityQueue.poll());//运行结果:4System.out.println(priorityQueue.poll());//        5}
}//实现大根堆的比较器
class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);//大根堆 两比较器仅有此处不同!!!!!!!!!!!!!!}
}
public class Test {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());priorityQueue.offer(4);priorityQueue.offer(5);priorityQueue.offer(6);System.out.println(priorityQueue.poll());//运行结果:6System.out.println(priorityQueue.poll());//        5}

3.2.3 PriorityQueue的扩容方式

以下是JDK17中的源码:

说明:

如果容量小于64时,按照oldCapacity的2倍方式扩容

如果容量大于等于64,按照oldCapacity的1.5倍方式扩容

如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容

3.3 OJ练习

top-k问题:最大或最小的前k个数据

    public static int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {minHeap.offer(arr[i]);}int[] tmp = new int[k];for (int i = 0; i < k; i++) {int val = minHeap.poll();tmp[i] = val;}return tmp;}public static void main(String[] args) {int[] array = {27,15,19,18,28};int[] ret = smallestK(array,3);System.out.println(Arrays.toString(ret));}

运行结果:

虽然上述方法也能满足需求,但是其时间复杂度为O((N+K)*\log _{2}N)

不是非常好的解决方案,现需要一个时间复杂度更小的方法:

若求前K个最小的数字

1. 先把前 个元素建立大小为K的大根堆

2. 遍历剩余 N-K 个元素,若堆顶元素大于当前 i 下标的值就出堆

这样遍历完数组后,大小为 K 的堆中就是最小的 K 个元素

反之求前K个最大的数字就建立小根堆

class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);//大根堆}
}
class Solution {public int[] smallestK(int[] arr, int k) {int[] tmp = new int[k];if(k == 0) {return tmp;}PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());//1.把前K个元素放进堆中for (int i = 0; i < k; i++) {maxHeap.offer(arr[i]);}//2.遍历剩下的 N-k 个元素for (int i = k; i < arr.length; i++) {int val = maxHeap.peek();if(val > arr[i]) {maxHeap.poll();maxHeap.offer(arr[i]);}}//3.将堆中元素放到数组中for (int i = 0; i < k; i++) {tmp[i] = maxHeap.poll();}return tmp;}
}

变种题:求第K小的数据,建立大根堆,堆顶元素就是第K小

3.4 堆排序

要求:在原堆上修改,不能新建

方法两步:

1. 建堆:

  • 要求升序,建大堆
  • 要求降序,建小堆

2. 利用堆删除来进行排序

建堆和堆删除中都用到了向下调整

    //堆排序 升序public void heapSort() {int endIndex = usedSize-1;while(endIndex > 0) {swap(0,endIndex);siftDown(0,endIndex);endIndex--;}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/360039.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[笔记] CCD相机测距相关的一些基础知识

1.35mm胶片相机等效焦距 https://zhuanlan.zhihu.com/p/419616729 拿到摄像头拍摄的数码照片后&#xff0c;我们会看到这样的信息&#xff1a; 这里显示出了两个焦距&#xff1a;一个是实际焦距&#xff1a;5mm&#xff0c;一个是等效焦距&#xff1a;25mm。 实际焦距很容易…

HarmonyOS Next 系列之可移动悬浮按钮实现(六)

系列文章目录 HarmonyOS Next 系列之省市区弹窗选择器实现&#xff08;一&#xff09; HarmonyOS Next 系列之验证码输入组件实现&#xff08;二&#xff09; HarmonyOS Next 系列之底部标签栏TabBar实现&#xff08;三&#xff09; HarmonyOS Next 系列之HTTP请求封装和Token…

Pytorch Geometric(PyG)入门

PyG (PyTorch Geometric) 是建立在 PyTorch 基础上的一个库&#xff0c;用于轻松编写和训练图形神经网络 (GNN)&#xff0c;适用于与结构化数据相关的各种应用。官方文档 Install PyG PyG适用于python3.8-3.12 一般使用场景&#xff1a;pip install torch_geometric 或conda …

百度地图3d区域掩膜,最常见通用的大屏地图展现形式

需求及效果 原本项目使用的是百度地图3.0,也就是2d版本的那个地图,客户不满意觉得不够好看,让把地图改成3d的,但是我们因为另外的系统用的都是百度地图,为了保持统一只能用百度地图做 经过3天的努力,最后我终于把这个效果实现了,效果如下: 如何引用GL版本 为了实现…

前端项目外包出去,是我痛苦的开始。如何破?

不止一个老铁给我反馈&#xff0c;他们把其前端项目外包出去&#xff0c;非常的痛苦&#xff0c;远不如用自己的员工省心。明面上钱省了&#xff0c;实际精力大量耗费在上面&#xff0c;一算账并没省&#xff0c;反而闹了一肚子气&#xff0c;问我这事该如何破&#xff1f;其实…

C#的无边框窗体项目模板 - 开源研究系列文章

继续整理和编写代码及博文。 这次将笔者自己整理的C#的无边框窗体项目的基本模板进行总结&#xff0c;得出了基于C#的.net framework的Winform的4个项目模板&#xff0c;这些模板具有基本的功能&#xff0c;即已经初步将代码写了&#xff0c;直接在其基础上添加业务代码即可&am…

Servlet组件

目录 1 我们为什么需要Servlet&#xff1f; 1.1 Web应用基本运行模式 1.2 Web服务器中Servlet作用举例 2 什么是Servlet&#xff1f; 3 如何使用Servlet&#xff1f; 3.1 操作步骤 3.2 运行分析(执行原理) 3.3 Servlet作用总结 4 Servlet生命周期 4.1 Servlet生命周期…

CRMEB 多门店后台登录入口地址修改(默认admin)

一、>2.4版本 1、修改后端 config/admin.php 配置文件,为自定义的后缀 2、修改 平台后台前端源码中 view/admin/src/settings.js 文件,修改为和上面一样的配置 3、修改后重新打包前端代码,并且覆盖到后端的 public 目录下&#xff1a;打包方法 4、重启swoole 二、<2.4版…

滑动窗口算法——部分OJ题详解

目录 关于滑动窗口 部分OJ题详解 209.长度最小的子数组 3.无重复字符的最长字串 1004.最大连续1的个数Ⅲ 1658.将x减到0的最小操作数 904.水果成篮 438.找到字符串中所有字母异位词 30.串联所有单词的子串 76.最小覆盖子串 关于滑动窗口 其实滑动窗口也是通过双指针…

项目性能优化之给dist文件夹中chunk-vendors.js做splitChunks分包,从而减少首屏加载时间

问题描述 我们项目做完&#xff0c;验收通过以后&#xff0c;就需要打包发布上线啦。于是我们执行命令&#xff1a;npm run build打dist包&#xff0c;打包完以后截图如下&#xff1a; 直接打包的chunk-vendors.js太大了 chunk-vendors.js文件太大了&#xff0c;所以我们需要…

软件测试基础知识

软件测试基础 一、软件测试质量 软件研发过程中&#xff0c;通常定义了2个软件质量相关的角色&#xff1a; QC就是测试人员&#xff0c;职责是尽可能早地发现软件的缺陷&#xff0c;并确保缺陷得到修复QA是流程的监督者&#xff0c;职责是创建和执行 改进软件开发过程&#x…

STARTRADER星迈:银和铜的未来前景,是否即将迎来历史新高?

随着全球经济的复苏和技术进步的加速&#xff0c;大宗商品市场特别是金属市场近年来表现出强劲的动态。2024年&#xff0c;包括白银和铜在内的大宗商品价格已连续创下多年和历史新高&#xff0c;被分析师誉为可能是大宗商品交易史上赚钱的一年。本文将STARTRADER外汇深入探讨白…

Chromium 开发指南2024 Mac篇-编译前的准备工作(一)

1.引言 Chromium 是一款开源的网页浏览器项目&#xff0c;作为 Google Chrome 浏览器的基础&#xff0c;其卓越的性能和广泛的应用使其成为众多开发者研究和学习的对象。对于希望深入了解浏览器内核&#xff0c;或是计划在 Chromium 基础上开发自定义浏览器的开发者来说&#…

在Tomcat中部署war包

1、准备war包 确保已经有一个有效的war包&#xff0c;该war包包含了web应用程序的所有内容&#xff1b; 2、停止tomcat服务器 在部署之前&#xff0c;确保tomcat服务器已经停止&#xff0c;进入tomcat的配置目录执行命令&#xff1a;[路径]/tomcat/conf&#xff1b; 在Linux…

EXCEL表格怎么批量删除日期后的时间?

竞价师最近有点忙了&#xff0c;因为百度新出来一个“线索有效性诊断”功能 一、下载电话、表单、咨询表格 二、选中整列 三、选中ctrlf 进行替换&#xff0c;日期输入空格&#xff0c;时间输入*&#xff0c;替换为空即可&#xff01; 四、整列单元格格式“日期”拉倒底部&…

线上OOM问题排查总结

自己搭建了一个小博客&#xff0c;该文章与博客文章同步。 一般情况下&#xff0c;出现OOM主要有一下三种原因。 一次性申请对象的太多。更改申请对象数量。内存资源耗尽未释放。找到未释放的对象进行释放。本身资源不够。jmap -heap 查看堆信息。 分几种情况解决&#xff1…

css文字镂空加描边

css文字镂空加描边 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>文字镂空</title><style>/* 公用样式 */html,body{width: 100%;height: 100%;position: relative;}/* html{overflow-y: scroll;} */*{margi…

C# 中的 StreamReader 和 StreamWriter 类

在这里插入代码片StreamReader 和 StreamWriter 位于 System.IO 命名空间中。当您想要读取或写入基于字符的数据时&#xff0c;这两个类都很有用。这两个类都处理 Unicode 字符。 StreamReader 派生自抽象类“TextReader”&#xff0c;StreamWriter 派生自“TextWriter”。 下…

爆火的儿童绘本如何用AI制作?一文解锁从制作到变现的全流程!

大家好我是安琪&#xff01; AI绘图发展势头如此猛烈&#xff0c;无论是Stable Diffusion&#xff0c;Midjourney&#xff0c;还是国内百度的文心一格&#xff0c;字节的豆包等&#xff0c;AI绘图技术越来越成熟&#xff0c;风格也越来越多样化。那么问题来了&#xff0c;对于普…

Linux企业 集群批量管理-秘钥认证

集群批量管理-秘钥认证 概述 管理更加轻松&#xff1a;两个节点&#xff0c;通过秘钥认证形成进行访问&#xff0c;不需要输入密码&#xff0c;单向服务要求&#xff08;应用场景&#xff09;&#xff1a; 一些服务在使用前要求我们做秘钥认证 手动写批量管理脚本名字&#x…