队列Queue-06

优先队列（Priority Queue）是一种抽象数据类型，它类似于常规的队列或栈，但每个元素都有一个优先级。在优先队列中，元素的出队顺序不是按照它们被添加的顺序，而是根据它们的优先级来决定。具有较高优先级的元素会先于具有较低优先级的元素出队。

1.基本概念
优先队列通常使用二叉堆（Binary Heap）来实现，其中最常见的是最小堆（Min Heap）和最大堆（Max Heap）。在最小堆中，父节点的值总是小于或等于其子节点的值；而在最大堆中，父节点的值总是大于或等于其子节点的值。这种结构允许优先队列在对数时间内完成插入和删除操作。

队列是遵循先进先出（First-In-First-Out）模式的，但有时需要在队列中基于优先级处理对象。

Queue 有一个直接子类 PriorityQueue

PriorityQueue 是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的 Comparator（比较器）在队列实例化的时排序。

优先队列的头是基于自然排序或者 Comparator 排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。
优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
PriorityQueue 是非线程安全的，所以 Java 提供了 PriorityBlockingQueue（实现 BlockingQueue 接口）用于 Java 多线程环境。
PriorityQueue 的底层数据结构是数组，而无边界的形容，那么指明了 PriorityQueue 是自带扩容机制的，具体请看 PriorityQueue 的 grow 方法。

PriorityQueue 可以作为堆使用，而且可以根据传入的 Comparator 实现大小的调整，会是一个很好的选择。

2.PriorityQueue 特点
按照自定义优先级排序

PriorityQueue 是一个支持优先级的无界阻塞队列;
默认自然顺序升序排序;
可以通过构造参数 Comparator 来对元素进行排序;
自定义实现 comapreTo()方法来指定元素排序规则。
不允许插入 null 元素。
实现 PriorityQueue 接口的类，不保证线程安全，除非是 PriorityBlockingQueue。
PriorityQueue 的迭代器不能保证以任何特定顺序遍历元素，如果需要有序遍历，请考虑使用Arrays.sort(pq.toArray)。
进列(offer、add)和出列（ poll、remove()）的时间复杂度 O(log(n))。
remove(Object) 和 contains(Object)的算法时间复杂度 O(n)。
peek、element、size 的算法时间复杂度为 O(1)。
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
3.操作方法
优先队列的基本操作包括：

插入（Insert）：将一个元素添加到队列中，并根据其优先级调整堆结构。
删除最高优先级元素（Delete Max/Min）：移除并返回具有最高优先级的元素，同时重新调整堆结构以保持其性质。
查找最高优先级元素（Find Max/Min）：返回具有最高优先级的元素，但不从队列中删除它。
更新优先级（Decrease Key/Increase Key）：改变队列中某个元素的优先级，并重新调整堆结构。
4.应用场景
优先队列在多种场景下都非常有用，包括但不限于：

任务调度：操作系统或实时系统中的任务调度，可以根据任务的优先级来决定执行顺序。
事件驱动模拟：在事件驱动的程序中，事件可以根据其发生的时间或重要性来排序。
图算法：如 Dijkstra 算法和 Prim 算法，它们在寻找最短路径或最小生成树时使用优先队列来选择下一个要处理的顶点或边。
作业调度：在批处理系统中，作业可以根据其优先级来决定其执行顺序。
5.PriorityQueue 继承与实现
在实际编程中，优先队列可以通过数组或链表来实现，但更高效的实现是使用二叉堆。在二叉堆中，每个元素的位置可以通过其索引来快速确定其父节点或子节点的位置，这大大简化了插入和删除操作。

PriorityQueue类继承了哪些类:

AbstractQueue 抽象类，具有队列的功能
PriorityQueue类实现了哪些接口:

Queue 接口，可作为队列使用。
6.性能说明
优先队列的性能主要取决于其底层数据结构。使用二叉堆实现的优先队列，插入和删除操作的时间复杂度为 O(log n)，查找最高优先级元素的操作是 O(1)。这使得优先队列在处理大量数据时非常高效。

7.总结
优先队列是一种强大的数据结构，它通过优先级来控制元素的处理顺序，非常适合需要根据元素重要性或紧迫性来排序的场景。无论是在系统设计、算法实现还是日常编程任务中，优先队列都是一种非常有用的工具。