今天要介绍的是基础容器类（为了与并发容器类区分开来而命名的名字）中的另一个成员——PriorityQueue，它的大名叫做优先级队列，想必即使没有用过也该有所耳闻吧，什么？没。。没听过？emmm。。。那就更该认真看看了。
通过本篇你将了解到：
1、PriorityQueue是什么？
2、PriorityQueue的内部结构是什么？
3、二叉堆、大顶堆、小顶堆分别是什么？有什么特性？
4、小顶堆是如何实现的，如何用数组表示？
5、小顶堆的删除、插入操作是如何进行的？
6、PriorityQueue的源码解析。
7、PriorityQueue的应用场景。
一、PriorityQueue简介PriorityQueue也是Queue的一个继承者，相比于一般的列表，它的特点便如它的名字一样，出队的时候可以按照优先级进行出队，所以不像LinkedList那样只能按照插入的顺序出队，PriorityQueue是可以根据给定的优先级顺序进行出队的。这里说的给定优先级顺序既可以是内部比较器，也可以是外部比较器。PriorityQueue内部是根据小顶堆的结构进行存储的，所谓小顶堆的意思，便是最小的元素总是在最上面，每次出队总是将堆顶元素移除，这样便能让出队变得有序，至于什么是小顶堆，后面会有详细介绍。
比如说，比较常见的场景就是任务队列，队列动态插入，后面的任务优先级高的需要被先执行，那么使用优先级队列就可以比较好的实现这样的需求。下面我们模拟一下这个场景：
public class PriorityQueueTest { public static void main(String[] args){ // 传入外部比较器， //PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority)); //PriorityQueue<Task> taskQueue = new PriorityQueue<>((t1, t2) -> t1.getPriority() - t2.getPriority()); PriorityQueue<Task> taskQueue = new PriorityQueue<>(new Comparator<Task>() { @Override public int compare(Task t1, Task t2) { return t1.getPriority() - t2.getPriority(); } }); // 添加六个任务 taskQueue.add(new Task(1, "learn java")); taskQueue.add(new Task(3, "learn c++")); taskQueue.add(new Task(4, "learn c#")); taskQueue.add(new Task(2, "learn python")); taskQueue.add(new Task(2, "learn php")); taskQueue.add(new Task(5, "learn js")); // 出队 while (!taskQueue.isEmpty()){ System.out.println(taskQueue.poll()); } } } class Task{ /** * 任务优先级 */ private int priority; /** * 任务名称 */ private String taskName; public Task() { } public Task(int priority, String taskName) { this.priority = priority; this.taskName = taskName; } public int getPriority() { return priority; } public void setPriority(int priority) { this.priority = priority; } public String getTaskName() { return taskName; } public void setTaskName(String taskName) { this.taskName = taskName; } @Override public String toString() { return "Task{" + "priority=" + priority + ", taskName='" + taskName + '\'' + '}'; } }