PriorityQueue详解(特点原理及使用示例)

PriorityQueue详解(特点原理及使用示例)-mikechen

PriorityQueue定义

PriorityQueue是Java集合框架中的一个实现了Queue接口的类,是 Java 中基于优先级的队列的通用实现。

 

PriorityQueue特点

PriorityQueue具有如下特点:

  1. PriorityQueue是一个基于优先级的队列,可以自动将元素按照指定的比较规则进行排序。
  2. PriorityQueue的底层实现是一个堆(Heap),默认是小根堆(即根节点最小)。
  3. PriorityQueue不允许插入null元素,并且元素必须实现Comparable接口。
  4. PriorityQueue的插入和删除元素的时间复杂度为O(logN),其中N为队列的大小。

 

PriorityQueue原理

PriorityQueue的底层实现是基于堆(Heap)数据结构的,是通过完全二叉树(complete binary tree)实现的小顶堆。

如下图所示:

PriorityQueue详解(特点原理及使用示例)-mikechen

堆是一种特殊的二叉树,满足以下两个性质:

  1. 堆序性质(Heap Property):对于堆中的每一个节点,它的值必须大于(或小于)它的子节点的值。
  2. 完全二叉树性质(Complete Binary Tree Property):堆必须是一棵完全二叉树,也就是说除了最后一层之外,其他层的节点都必须是满的。

堆分为大根堆和小根堆,它们的区别在于根节点的值,在大根堆中,根节点的值最大,而在小根堆中,根节点的值最小,PriorityQueue默认是小根堆。

PriorityQueue中每个元素都是一个节点,节点之间是按照完全二叉树的形式排列的。

为了满足堆序性质,PriorityQueue维护了一个二叉堆结构,并对元素进行排序。

 

PriorityQueue使用

1.PriorityQueue常用方法

  • 插入元素:可以使用offer()或add()方法来插入元素,如果元素超过了队列的容量,PriorityQueue会自动扩容。
  • 删除元素:可以使用poll()或remove()方法来删除队头元素,这会将队头元素从队列中删除并返回它。
  • 查看队头元素:可以使用peek()方法来查看队头元素,但是不会从队列中删除它。
  • 判断队列是否为空:可以使用isEmpty()方法来判断队列是否为空。

方法

说明

add(E e)

添加元素,如果超过队列长度,抛出异常

offer(E e)

添加元素,如果超过队列长度返回false

remove()

获取下个元素,如果没有抛出异常

poll()

获取下个元素,如果没有返回null

element()

查看下个元素的内容,如果没有抛异常

peek()

查看下个元素的内容,如果没有返回null

 

2.PriorityQueue使用示例

PriorityQueue使用跟普通队列一样,唯一区别是PriorityQueue会根据排序规则决定谁在队头,谁在队尾。

如下所示:

import java.util.*;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个默认的小根堆PriorityQueue
        PriorityQueue pq = new PriorityQueue<>();

        // 插入元素
        pq.offer(3);
        pq.offer(1);
        pq.offer(2);

        // 删除元素
        System.out.println(pq.poll()); // 输出1

        // 查看队头元素
        System.out.println(pq.peek()); // 输出2

        // 判断队列是否为空
        System.out.println(pq.isEmpty()); // 输出false
    }
}

以上就是PriorityQueue的详解,更多Java集合框架,请查看:Java集合框架详解(看这篇就够了)

作者简介

陈睿|mikechen,10年+大厂架构经验,BAT资深面试官,就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号,获取更多技术干货!

后台回复架构,即可获取《阿里架构师进阶专题全部合集》,后台回复面试即可获取《史上最全阿里Java面试题总结

评论交流
    说说你的看法