前言：

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

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

八大排序之选择排序_冷兮雪的博客-CSDN博客

1、PriorityQueue的特性

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

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

关于PriorityQueue的使用要注意：
使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常
不能插入null对象，否则会抛出NullPointerException
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
插入和删除元素的时间复杂度为log₂N
PriorityQueue底层使用了堆数据结构,
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>() {@Overridepublic 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());//2PriorityQueue<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;@Overridepublic 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
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 codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

优先级队列的扩容说明：

如果容量小于64时，是按照oldCapacity的2倍方式扩容的
如果容量大于等于64，是按照oldCapacity的1.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 个出现次数最多的单词。