【Java--数据结构】优先级队列（ PriorityQueue）

server/2025/3/18 0:48:43/

一. 优先级队列

1.1  优先级队列的概念

优先级队列是一种特殊的队列，它在入队时会根据元素的优先级进行排序，优先级最高的元素排在队列的前面，出队时会优先出队优先级最高的元素。

1.2 优先级队列的区别

（1）与普通队列的区别

  1. 普通队列是先进先出的，元素按照入队的顺序依次出队。
  2. 优先级队列不考虑入队的先后顺序，只根据元素的优先级来决定出队顺序

（2）与栈的区别

  1. 栈是后进先出的，最后入栈的元素最先出栈。
  2. 优先级队列则根据优先级决定出队顺序，与入队顺序无关。

核心特点：元素按优先级排序，每次取出优先级最高（或最低）的元素 

二. 堆

PriorityQueue类底层使用堆这种数据结构，堆适用于完全二叉树

2.1 堆的概念

堆是一种特殊的完全二叉树数据结构

完全二叉树：除了最后一层外，每一层的节点数都是满的，并且最后一层的节点都靠左排列。

堆的分类：

（1）最大堆：父节点 ≥ 子节点，根节点为全局最大值。

（2）最小堆：父节点 ≤ 子节点，根节点为全局最小值。

2.2 堆的性质

（1）堆序性：

  1. 根节点是堆中的最大元素（大根堆）或最小元素（小根堆）
  • 比如：在大根堆中，根节点（第一层）值大于等于第二层子节点的值，第二层子节点的值又大于等于第三层子节点的值，以此类推。

（2）完全二叉树：

  1. 所有层（除最后一层）必须完全填满

  2. 最后一层的节点必须从左到右连续，不能出现中间空缺

注意：

节点关系下标计算公式
父节点parent = (i-1)/2
左子节点left = 2*i + 1
右子节点right = 2*i + 2

2.3 堆的操作

（1）向下调整

常用于创建堆和删除操作

主要步骤：

循环条件：子节点的下标小于总数

  1. 根据父亲节点找到字节点
  2. 比较得出左右节点的最大节点
  3. 比较父节点和最大节点，如果左右最大节点大于父节点，则交换
  4. 父亲节点等于字节点

代码实现：

    //向下调整public void shiftDown(int i ,int usedSize){int child = (i*2)+1;//左孩子while (child<usedSize) {if (child + 1 < usedSize && elem[child] < elem[child + 1]) {child++;}if (elem[child] > elem[i]) {swap(child,i);i = child;child = (i*2)+1;}else {break;}}}

（2）向上调整

常用于增加操作

 主要步骤：

循环条件：子节点的下标大于0

  1. 找出子节点的父亲节点
  2. 与父亲节点进行大小比较，大于则交换
  3. 让子节点等于父亲

 代码实现：

    //向上调整public void shiftUp(int child){int parent = (child-1)/2;while (child>0) {if (elem[parent] < elem[child]) {swap(parent, child);child = parent;parent = (child - 1) / 2;} else {break;}}}

（3）堆的创建（最大堆）

从最后一个非叶子节点开始，自底向上逐个向下调整

主要步骤：

  1. 得到最大下标的父亲节点（最后一个非叶子节点）
  2. 向下调整

代码实现： 

 public void createHeap(){//找出最大的根节点for (int i = (usedSize-1-1)/2; i >=0 ; i--) {shiftDown(i,usedSize);}}//向下调整public void shiftDown(int i ,int usedSize){int child = (i*2)+1;//左孩子while (child<usedSize) {if (child + 1 < usedSize && elem[child] < elem[child + 1]) {child++;}if (elem[child] > elem[i]) {swap(child,i);i = child;child = (i*2)+1;}else {break;}}}

（4）堆的插入

主要步骤：

  1. 将插入的元素放入最后一位
  2. 向上调整
  3. 堆的元素个数加一个

代码实现：

    public void offer(int val){if(isFull()){this.elem = Arrays.copyOf(elem,elem.length+1);}else {elem[usedSize] = val;shiftUp(usedSize);usedSize++;}}

注意：必须是在已经有序的基础上插入 

（5）堆的删除

堆的删除是删除栈顶元素

主要步骤：

  1. 将栈顶元素和最后一个元素进行交换
  2. 堆中的元素总数减少一个
  3. 栈顶元素向下调整

 代码实现：

    public int poll(){int tmp = elem[0];swap(0,usedSize-1);usedSize--;shiftDown(0,usedSize);return tmp;}

（6）堆的排序

最大堆——由小到大

主要步骤：

  1. 交换堆顶与末尾元素
  2. 调整剩余堆
  3. 重复直至有序

代码实现：

    //排序从小 到大public void heapSort(){int end = usedSize-1;while(end>0){swap(0,end);shiftDown(0,end);end--;}}

三. PriorityQueue

3.1 PriorityQueue的特性

 注意：

  1. PriorityQueue底层使用堆数据结构
  2. 默认情况下生成的是最下堆，如果想要生成最大堆可以通过使用比较器
  3. 时间复杂度：插入和删除O(log2n)。
  4. 堆中不能存放 null对象
  5. 堆中存放的元素必须要可以比较
  6. 使用时要导入PriorityQueue所在的包

3.2 PriorityQueue的使用

1. 构造方法

(1) 无参构造

Priority( )

        PriorityQueue<Integer> queue = new PriorityQueue<>();

 注意：无参构造方法，没有给定大小，默认容量为11

(2) 有参构造

PriorityQueue(int initialCapacity)

PriorityQueue<Integer> queue1 = new PriorityQueue<>(100);

注意：在调用有参构造器时，传入的参数不能小于1，不然会报错

(3) 利用Collection构建

PriorityQueue(Collection <? extends E>c)

import java.util.PriorityQueue;public class Text_1 {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();PriorityQueue<Integer> queue1 = new PriorityQueue<>(100);queue1.offer(12);queue1.offer(3);queue1.offer(9);PriorityQueue<Integer> queue2 =new PriorityQueue<>(queue1);queue2.offer(999);System.out.println(queue2);}
}
//输出：[3, 12, 9, 999]

注意：

在使用PriorityQueue类的时候，不要忘记导入包 

2. 基本操作

（1）插入

插入元素，插入成功返回true，如果插入内容为空，抛出异常

import java.util.PriorityQueue;public class Offer {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);System.out.println(queue);}
}

注意： 空间不够时候会自动进行扩容

（2）删除

移除优先级最高的元素并返回，如果优先级队列为空，返回null

import java.util.PriorityQueue;public class Poll {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);int x = queue.poll();System.out.println(x);}
}
（3）获取

获取优先级最高的元素，如果优先级队列为空，返回null

import java.util.PriorityQueue;public class Peek {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);int x = queue.peek();System.out.println(x);}
}
（4）大小

获取有效元素的个数

import java.util.PriorityQueue;public class Size {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);int x = queue.size();System.out.println(x);}
}
（5）清空
import java.util.PriorityQueue;public class IsEmpty {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);boolean x = queue.isEmpty();System.out.println(x);queue.clear();boolean x1 = queue.isEmpty();System.out.println(x1);}
}
（6）判空

检测优先级队列是否为空，空返回true

import java.util.PriorityQueue;public class IsEmpty {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);boolean x = queue.isEmpty();System.out.println(x);queue.clear();boolean x1 = queue.isEmpty();System.out.println(x1);}
}

3.3 练习

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

求前k最大元素--使用最小堆

求前k最小元素--使用最大堆

（1）求前k个最大元素

方法1：使用最大堆（不推荐，如果数据太多，时间复杂度会很大，很占用内存）

主要步骤：

  1. 将数组内所有元素放入优先级队列中
  2. 每次删除队列中的最大值
  3. 将最大值赋值给新的数组内
    public int[] maxKK(int[] arr, int k) {int[] ret = new int[k];if(arr==null||k<=0){return ret;}//默认最小堆，通过使用比较器，变成默认最大堆PriorityQueue<Integer> queue = new PriorityQueue<>(arr.length);for (int i = 0; i < arr.length; i++) {queue.offer(arr[i]);}//每次弹出的就是最大的for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}

方法2： 使用最小堆

刷新每一次下限（最小值）

主要步骤：

  1. 先将数组内的前k个元素放进优先级队列里
  2. 从第k个元素往后开始逐个比较，如果k下标的值比队列的最小值大，那就删除最小元素，添加这个元素
  3. 每次都去掉最小的元素，那么就剩下了最大的
    //找出最大的k个数public int[] maxK(int[] array,int k){int[] ret = new int[k];if(k<=0||array == null){return ret;}PriorityQueue<Integer> queue = new PriorityQueue<>(k);for (int i = 0; i < k; i++) {queue.offer(array[i]);}for (int i = k; i < array.length; i++) {int x = queue.peek();if(array[i]>x){queue.poll();queue.offer(array[i]);}}for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}
（2）求前k个最小元素

使用最大堆

刷新每一次上限（最大值）

主要步骤：

  1. 先将数组内的前k个元素放进优先级队列里
  2. 从第k个元素往后开始逐个比较，如果k下标的值比队列的最大值小，那就删除最大元素，添加这个元素
  3. 每次都去掉最大的元素，那么就剩下了最小的
 public int[] MinK(int[] array,int k){int[] ret = new int[k];if(k<=0||array == null){return ret;}PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());//将数组的前k个元素入队列for (int i = 0; i < k; i++) {queue.offer(array[i]);}for (int i = k; i < array.length; i++) {//队列中的最大值int x = queue.peek();//将最大的弹出去，将这个小的放进来if(array[i] < x){queue.poll();queue.offer(array[i]);}}//将队列中的最大值依次放入数组for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}

点赞的宝子今晚自动触发「躺赢锦鲤」buff！


http://www.ppmy.cn/server/175818.html

相关文章

Spring Retry

Spring Retry

1. Spring Retry 的工作原理 内部机制 Spring Retry 主要通过 AOP&#xff08;面向切面编程&#xff09;实现重试逻辑。以下是 Spring Retry 的内部工作流程&#xff1a; AOP 拦截器&#xff1a;当一个方法被标记为需要重试&#xff0c;并且该方法抛出了指定类型的异常时&am…
阅读更多...
[RN 实践有效]Expo+cross-env配置项目环境变量

[RN 实践有效]Expo+cross-env配置项目环境变量

首先，从中可以看出，cross-env的主要作用是跨平台设置环境变量，而Expo项目通常通过app.config.js或.env文件来管理这些变量。需要强调安装cross-env的必要性，以及如何在package.json中正确配置脚本命令。 接下来，用户的问题是关于Expo中cross-env的详细配置，因此需要分步骤…
阅读更多...
Maven核心包：maven-resolver-api

Maven核心包：maven-resolver-api

在阅读 nexus-pubic 开源项目过程中&#xff0c;使用了大量的核心组件进行轻量化集成。它的这种构建方式&#xff0c;在阅读过程中不得不感概&#xff0c;节省成本从构建项目的方式上就遥遥领先了。但是 maven核心包&#xff0c;依然使用前几年的aether-spi&#xff0c;却没有更…
阅读更多...
[网络] 网络基础概念--socket编程预备

[网络] 网络基础概念--socket编程预备

文章目录 1. 理解 ip 地址和目的 IP 地址 -> 区分主机唯一性2. 认识端口号3. socket 套接字4. 传输层的代表协议 -> tcp & udp5. 网络字节序列 -> 大端序列6. socket 编程接口 继前文, 前文提到了网络传输的基本流程, 那下面我们继续来讨论一点关于网络基础概念的…
阅读更多...
ubuntu-linux-系统用户界面无法显示-弹出报警框！

ubuntu-linux-系统用户界面无法显示-弹出报警框！

文章目录 简介方法一&#xff1a;使用第二用户使用文本控制台 方法二&#xff1a;结语扩展&#xff08;请务必阅读&#xff09; 简介 请创建第二用户或者准备u盘启动盘&#xff08;ubuntu系统就行&#xff09;&#xff01; 原因&#xff1a;本人电脑在后续的开机过程中&#x…
阅读更多...
QT信号与槽：实现方法、技术细节、高级用法和底层机制

QT信号与槽：实现方法、技术细节、高级用法和底层机制

1. 基本概念 信号&#xff08;signals&#xff09;&#xff1a;当对象的状态发生变化或发生特定事件时&#xff0c;自动触发的通知。比如PushButton常见的信号是clicked()信号。 槽&#xff1a;接收信号并执行逻辑的成员函数。可定义在类的任何部分&#xff08;public、priva…
阅读更多...
【leetcode hot 100 199】二叉树的右视图

【leetcode hot 100 199】二叉树的右视图

解法一&#xff1a;层级遍历&#xff0c;右侧看到的节点就是每一层最后一个元素 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }…
阅读更多...
Chrome/Edge浏览器离线安装插件全攻略：CRX/ZIP文件手动安装教程

Chrome/Edge浏览器离线安装插件全攻略：CRX/ZIP文件手动安装教程

&#x1f527; 准备工作 从可信渠道下载扩展文件&#xff1a; .crx 格式&#xff08;Chrome/Edge原生插件包&#xff09;.zip 格式&#xff08;已解压的插件文件夹&#xff09; &#x1f4a1; 推荐下载源&#xff1a; Chrome插件镜像站 &#x1f6e0;️ 详细安装步骤 步骤1&a…
阅读更多...
最新文章

Copyright @ 2022~2023