优先级队列

简介: 优先级队列

前言:

普通的队列是一种 先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用 数据结构来实现。

在下面这篇文章中讲解了堆。

1、PriorityQueue的特性

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

查看源码发现:PriorityQueue继承了AbstractQueue,并且初始容量为11,AbstractQueue又实现了Queue接口


921ce77aaada496282d0a8ade14ff150.pngadc7b7f73bcd4db8850d5b64db35610a.png

c8ba7ec814f6433e84100172ae3d6329.png

关于PriorityQueue的使用要注意:

  1.  使用时必须导入PriorityQueue所在的包,即:
import java.util.PriorityQueue;
  1. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException异常
  2. 不能插入null对象,否则会抛出NullPointerException
  3.  没有容量限制,可以插入任意多个元素,其内部可以自动扩容
  4. 插入和删除元素的时间复杂度为log₂N
  5. PriorityQueue底层使用了堆数据结构,
  6.  PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素(如果要设置为大根堆的话需要重写比较器来实现或者借助lambda表达式
package 选择排序;
import java.util.PriorityQueue;
public class 优先级队列 {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        queue.offer(4);
        queue.offer(2);
        queue.offer(3);
        queue.offer(7);
        queue.offer(9);
        System.out.println(queue.peek());//2
    }
}

方法一:比较器

PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

方法二:lambda表达式

Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
import java.util.Comparator;
import java.util.PriorityQueue;
public class 优先级队列 {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(4);
        queue.offer(2);
        queue.offer(3);
        queue.offer(7);
        queue.offer(9);
        System.out.println(queue.peek());//2
        PriorityQueue<Integer> queue1=new PriorityQueue<>((o1, o2) -> o2-o1);
        queue1.offer(4);
        queue1.offer(2);
        queue1.offer(3);
        queue1.offer(7);
        queue1.offer(9);
        System.out.println(queue1.peek());//9
    }
}

2 PriorityQueue常用接口介绍

Ⅰ、PriorityQueue常见的构造方法


image.png

import java.util.PriorityQueue;
class Student implements Comparable<Student>{
    public int age;
    @Override
    public int compareTo(Student o) {//如果没有比较器,则下面添加时则会报错
        return this.age-o.age;
    }
}
public class 优先级队列 {
    public static void main(String[] args) {
        PriorityQueue<Student> queue=new PriorityQueue<>();
        queue.offer(new Student());
        queue.offer(new Student());
    }
}

因为PriorityQueue不能插入无法比较大小的对象,需要实现比较器。


09b3aab704e64092ae5339fec155e025.png

Ⅱ、常用的方法

Modifier and Type Method and Description
boolean
add(E e)
将指定的元素插入到此优先级队列中。
void clear()
从此优先级队列中册除所有元素。
Comparatore<? super E>

comparator(

返回用于为了在这个队列中的元素,或比较null如果此队列根据所述排序natural ordering的元素。

boolean contains(object o)
如果此队列包含指定的元素,则返回true.
Iteratore<E> iterator()
返回此队列中的元素的迭代器。
boolean offer(E e)
将指定的元素插入到此优先级队列中。
E peek ()
检素但不删除此队列的头,如果此队列为空,则返回null.
E poll()
检索并删除此队列的头,如果此队列为空,则返回null。
boolean remove(object o)
从该队列中删除指定元素的单个实例(如果存在)。
int size()
返回此集合中的元素数。
object[] toArray()
返回一个包含此队列中所有元素的数组。
<T>  T[]

toArray(T[]a)
返回一个包含此队列中所有元素的数组;返回的数组的运行时类型是指定数组的运行时类型。

Ⅲ、PriorityQueue的扩容方式:

private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

优先级队列的扩容说明:

  • 如果容量小于64时,是按照oldCapacity2倍方式扩容的
  • 如果容量大于等于64,是按照oldCapacity1.5倍方式扩容的
  • 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容




e7e9c12949e54d53b767af95ea682d89.png

3、应用

经典优先级队列问题——TOP-K问题:最大或者最小的前k个数据

面试题 17.14. 最小K个数 - 力扣(Leetcode)

class Solution {
    public int[] smallestK(int[] arr, int k) {
// 参数检测
        if (null == arr || k <= 0)
            return new int[0];
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
// 将数组中的元素依次放到堆中
        for (int i = 0; i < arr.length; ++i) {
            q.offer(arr[i]);
        }
// 将优先级队列的前k个元素放到数组中
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = q.poll();
        }
        return ret;
    }
}

692. 前K个高频单词 - 力扣(Leetcode)

这题既可以使用HashMap也可以使用优先级队列。


优先级队列思想

我们可以创建一个小根优先队列(顾名思义,就是优先队列顶端元素是最小元素的优先队列)。我们将每一个字符串插入到优先队列中,如果优先队列的大小超过了 k,那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k个元素就是前 k 个出现次数最多的单词。











目录
相关文章
|
2天前
|
云安全 数据采集 人工智能
古茗联名引爆全网,阿里云三层防护助力对抗黑产
阿里云三层校验+风险识别,为古茗每一杯奶茶保驾护航!
古茗联名引爆全网,阿里云三层防护助力对抗黑产
|
3天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
465 1
kde
|
3天前
|
人工智能 关系型数据库 PostgreSQL
n8n Docker 部署手册
n8n是一款开源工作流自动化平台,支持低代码与可编程模式,集成400+服务节点,原生支持AI与API连接,可自托管部署,助力团队构建安全高效的自动化流程。
kde
315 3
|
2天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段四:学术分析 AI 项目 RAG 落地指南:基于 Spring AI 的本地与阿里云知识库实践
本文介绍RAG(检索增强生成)技术,结合Spring AI与本地及云知识库实现学术分析AI应用,利用阿里云Qwen-Plus模型提升回答准确性与可信度。
215 91
AI 超级智能体全栈项目阶段四:学术分析 AI 项目 RAG 落地指南:基于 Spring AI 的本地与阿里云知识库实践
|
4天前
|
传感器 人工智能 算法
数字孪生智慧水务系统,三维立体平台,沃思智能
智慧水务系统融合物联网、数字孪生与AI技术,实现供水全流程智能监测、预测性维护与动态优化。通过实时数据采集与三维建模,提升漏损控制、节能降耗与应急响应能力,推动水务管理从经验驱动迈向数据驱动,助力城市水资源精细化、可持续化管理。
275 143
|
18天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
7天前
|
人工智能 移动开发 自然语言处理
阿里云百炼产品月刊【2025年9月】
本月通义千问模型大升级,新增多模态、语音、视频生成等高性能模型,支持图文理解、端到端视频生成。官网改版上线全新体验中心,推出高代码应用与智能体多模态知识融合,RAG能力增强,助力企业高效部署AI应用。
346 1

热门文章

最新文章