优先级队列

这篇具有很好参考价值的文章主要介绍了优先级队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

 前言:

1、PriorityQueue的特性

.2 PriorityQueue常用接口介绍

Ⅰ、PriorityQueue常见的构造方法

 Ⅱ、常用的方法

Ⅲ、PriorityQueue的扩容方式:

 3、应用


 前言:

普通的队列是一种 先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用 数据结构来实现。
在下面这篇文章中讲解了堆。
八大排序之选择排序_冷兮雪的博客-CSDN博客

1、PriorityQueue的特性

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

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

优先级队列

 优先级队列

优先级队列

关于PriorityQueue的使用要注意:
  1.  使用时必须导入PriorityQueue所在的包,即: 
    import java.util.PriorityQueue;
  2.  PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException异常
  3. 不能插入null对象,否则会抛出NullPointerException
  4.  没有容量限制,可以插入任意多个元素,其内部可以自动扩容
  5. 插入和删除元素的时间复杂度为log₂N
  6. PriorityQueue底层使用了堆数据结构,
  7.  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常见的构造方法

构造器
解释
PriorityQueue()
创建一个空的优先级队列,默认容量是 11
PriorityQueue(int
initialCapacity)
创建一个初始容量为 initialCapacity 的优先级队列,注意:
initialCapacity不能小于1 ,否则会抛 IllegalArgumentException 异 常
PriorityQueue(Collection<?
extends E> c)
用一个集合来创建优先级队列
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不能插入无法比较大小的对象,需要实现比较器。

优先级队列

 Ⅱ、常用的方法

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来进行扩容

优先级队列

 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 个出现次数最多的单词。文章来源地址https://www.toymoban.com/news/detail-434570.html

到了这里,关于优先级队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【CSS】CSS 特性 ( CSS 优先级 | 优先级引入 | 选择器基本权重 )

    定义 CSS 样式时 , 可能出现  多个 类型相同的 规则   定义在 同一个元素上 , 如果 CSS 选择器 相同  ,  执行 CSS 层叠性  , 根据  就近原则  选择执行的样式 , 如 : 出现两个 div 标签选择器 , 都设置 color 文本颜色 ; 如果 CSS 选择器 不同 ,  则需要考虑 CSS 优先级 问题 ,  需要计

    2024年02月10日
    浏览(54)
  • 【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

    前言: 大家好,我是 良辰 丫💞💞⛽,我们又见面了,前面我们讲了用链表实现的二叉树,今天我们来接触 堆 的概念,堆是一种特殊的二叉树,只不过咱们的对底层原理是数组,堆也是我们在做题中经常见到的,那么,接下来我们就慢慢的去接触堆, 认识堆,理解堆,掌

    2024年02月02日
    浏览(53)
  • Linux_进程的优先级&&环境变量&&上下文切换&&优先级队列

    什么是优先级? 指定一个进程获取某种资源的先后顺序 本质是进程获取cpu资源的优先顺序 为什么要有优先级 进程访问的资源(CPU)是有限的 操作系统关于调度和优先级的原则:分时操作系统,基本的公平,如果进程因为长时间不被调整,就造成了饥饿问题 Linux的优先级特

    2024年04月09日
    浏览(57)
  • 优先级队列

    目录  前言: 1、PriorityQueue的特性 .2 PriorityQueue常用接口介绍 Ⅰ、PriorityQueue常见的构造方法  Ⅱ、常用的方法 Ⅲ、PriorityQueue的扩容方式:  3、应用 普通的队列是一种 先进先出 的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元

    2024年02月02日
    浏览(64)
  • 优先级队列【C++】

    优先队列(priority_queue)也是队列的一种,priority_queue的接口是和queue的接口是相同的。所以两者的使用语法也是相同的。我们直接看优先队列(priority——queue)的底层实现原理。 默认情况下priority_queue是大堆。 priority_queue的底层实际上就是堆,模拟实现priority_queue之前,需要

    2024年02月10日
    浏览(44)
  • rabbitmq的优先级队列

    在我们系统中有一个 订单催付 的场景,我们的客户在天猫下的订单 , 淘宝会及时将订单推送给我们,如果在用户设定的时间内未付款那么就会给用户推送一条短信提醒,很简单的一个功能对吧,但是,tianmao商家对我们来说,肯定是要分大客户和小客户的对吧,比如像苹果,

    2024年02月11日
    浏览(47)
  • 「数据结构」优先级队列

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! 优先级队列底层是用堆实现的 ,关于堆的实现,之前的文章已经详细介绍过了,文章链接:二叉树1:堆的实现 方法 功能 PriorityQueue() 创建一个空的优先级队列,默认容量是11 PriorityQueue(int i

    2024年02月20日
    浏览(43)
  • Java优先级队列-堆

    大家好,我是晓星航。今天为大家带来的是 Java优先级队列(堆) 的讲解!😀 使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中。 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。 这种方式的主要用法就是堆的表示。 已知双亲(parent)的下

    2023年04月16日
    浏览(40)
  • 【JAVA】优先级队列(堆)

    羡慕别人就让自己变得更好! 优先级队列(堆)可用于topK问题 有大小根堆 注意堆的模拟实现 坚持真的很难但是真的很酷! 队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列。 此时,数据结

    2024年02月15日
    浏览(50)
  • CSS_三大特性下_优先级

    CSS_特性继承和层叠 - Bublly - 博客园 (cnblogs.com) CSS_特性继承和层叠 - Bublly - 博客园 (cnblogs.com) 1特性: 不同选择器具有不同的优先级,优先级高的选择器样式会覆盖优先级低选择器样式 2优先级公式: 继承通配符选择器标签选择器类选择器id选择器行内样式!important 3注意点:

    2024年02月08日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包