优先级队列
优先级队列是一种特殊的队列，每个元素都有一个优先级或者权重，与普通队列的先进先出不同，它按照优先级的大小从高到低进行排序，优先级最高的优先出队列。在任务调度，事件模拟中发挥着重要的作用。
Java中的优先级队列是一种利用堆这种数据结构进行实现，按照数据的优先级顺序进行排序，可以任意的顺序插入，但是取出时按照规定好的优先级进行操作。
堆
将自身的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中，分为大根堆和小根堆。
大根堆是任意节点大于它的孩子节点，小根堆是任意节点小于它的孩子节点。
观察小根堆的逻辑结构，第二层中的40大于第三层的20和30，这是因为小根堆只要求根节点小于孩子节点即可，不要误以为上一层的节点一定小于下一层的节点。大根堆同理。
由于堆的存储方式根据按照数组进行存储以及逻辑结构是完全二叉树，因此根据下标的对应关系，可以得到：
- parent = (child-1)/2;
- leftchild = parent*2+1;
- rightchild = parent*2+2;
注意：父节点的下标范围在[0,(n-1-1)/2],孩子节点的下标范围[1,n-1],其中n为数组的长度。
n-1指的是最后一个下标的位置，当child是右孩子的时候，（n-1）/2并不能正确的找到父节点（找到的是parent+1）,因此正确的是(n-1-1)/2。举个例子：数组长度为7，那么n==7,父节点为2，那么左孩子为2*2+1=5,右孩子为2*2+2=6，对于右孩子(n-1-1)/2-->(5/2==2)是正确的值。
向上调整和向下调整
给出一个数组，应该如何将它变成大根堆或者小根堆呢？
堆的插入实际是调整交换数组中元素，以大根堆为例，如果数组为空，元素直接作为第一个位置，逻辑结构中位于根节点，再来一个元素，比较与父节点的值，如果大于父节点，和进行交换，否则直接插入。例如：有这样的一个堆结构，[8,6,3,2,5,2,1]先将插入一个7
看到父节点(2),比自己小，进行交换得到[8,6,3,7,5,2,1,2]，看到父节点(6)，比自己小，进行交换得到[8,7,3,6,5,2,1,2],看到父节点8,比自己大，停止交换。最终得到的大根堆为：
因此可以得到堆的向上调整代码：
// i位置的数，向上调整大根堆，i这里指的是下标（有0），不是长度（没有0）// arr[i] = x，x是新来的数字public static void heapInsert(int i) {// 比父节点值大while (arr[i] > arr[(i - 1) / 2]) {// 交换swap(i, (i - 1) / 2);// 移动到父节点i = (i - 1) / 2;}}那么如果遇到这一种情况呢，还是原先的[8,6,3,2,5,2,1]，现在如果根节点的数值8变为了数值3，那么如何进行堆的维护。
再有孩子节点的情况下，找出孩子节点的最大值，进行交换，依次往下，直到来到正确的位置。
例如：对于[3,6,3,2,5,2,1]，3（0下标）孩子的最大值是6（1下标），交换变为[6,3,3,2,5,2,1],3(1位置)孩子的最大值为5（4下标）交换变为[6,5,3,2,3,2,1]，没有了孩子节点，达到了正确位置，最终得到的逻辑结构为：
代码如下：
// i位置的数改变，向下调整大根堆// 当前堆的大小为sizepublic static void heapify(int i, int size) {// 它的左孩子int l = i * 2 + 1;// 不越界while (l < size) {// 右孩子不越界+找左右孩子的最大值下标int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;// 当前的和它的最大孩子，谁是最大的best = arr[best] > arr[i] ? best : i;// 自己大，不用换了if (best == i) {break;}// 孩子大，进行交换swap(best, i);// 走到进行交换的孩子下标i = best;// 找下一个孩子l = i * 2 + 1;}}堆的插入
当向一个堆的插入新的元素时，像将其存储到数组最后一个位置，然后向上调整维持堆的结构，下图为向大根堆插入新元素15的向上调整过程：
那么插入的代码为：
public void offer(int val) {if(isFull()) {throw new ElemIsFullException("数组满了");}// 最后一个位置插入arr[usedSize] = val;// 向上调整堆结构heapInsert(usedSize);// 使用空间+1usedSize++;}
// 向上调整代码 -- 在上面堆的删除
堆的删除一般指的是删除堆顶的元素：将堆顶元素与最后一个元素交换，删除最后一个元素，向下调整，维持堆的结构。删除代码如下：
public int poll() {if(isEmpty()) {throw new ElemIsEmptyException("无元素可以删除！");}// 交换最后一个元素与第一个元素swap(arr[usedSize-1],arr[0]);// 删除最后一个元素usedSize--;// 根节点向下调整heapify(0, usedSize);return ret;}// 向下调整代码 -- 在上面堆排序
建立大根堆或者小根堆，获取堆顶元素，每次进行弹出，进行堆得调整，获取的顺序就是递减或者递增的顺序。
// 从顶到底建立大根堆，O(n * logn)// 依次弹出堆内最大值并排好序，O(n * logn)// 整体时间复杂度O(n * logn)public static void heapSort1() {for (int i = 0; i < n; i++) {heapInsert(i);}int size = n;while (size > 1) {swap(0, --size);heapify(0, size);}}// 从底到顶建立大根堆，O(n)// 依次弹出堆内最大值并排好序，O(n * logn)// 整体时间复杂度O(n * logn)public static void heapSort2() {for (int i = n - 1; i >= 0; i--) {heapify(i, n);}int size = n;while (size > 1) {swap(0, --size);heapify(0, size);}}模拟实现PriorityQueue
- 在Java的集合框架中，PriorityQueue是一个基于优先级堆实现的无界队列，它的容量是按照存储元素的实际数量进行调整。
- 优默认情况下是小根堆，但是可以通过Comparator来指定元素的优先级
- 不允许使用null元素也不允许插入不可比较的对象，即队列中的元素必须能够排序，因此放入的元素必须实现Comparable接口或者构造优先级队列时自定义Comparator来指定优先级
- 时间复杂度为O(logn)
构造方法的演示
1.默认构造方法
创建一个空的优先级队列，元素按照自然的顺序进行排序
PriorityQueue<E>()
// 实际使用
PriorityQueue<Integer> defaultPQ = new PriorityQueue<>();2.指定初始容量的构造方法
创建一个空的优先级队列并指定初始容量，但是不能小于1，元素按照自然的顺序进行排序
PriorityQueue<E>(int initialCapacity)
// 实际使用
PriorityQueue<Integer> capacityPQ = new PriorityQueue<>(10);3.使用集合构造方法
使用给定集合中的元素创建一个优先级队列，按照自然顺序排序
PriorityQueue<E>(Collection<? extends E> c)
// 实际使用
ArrayList<Integer> list = new ArrayList<>();
list.add(3);
list.add(7);
list.add(10);
PriorityQueue<Integer> collectionPQ = new PriorityQueue<>(list);4.使用比较器
创建空的优先级队列，并指定比较器排序
PriorityQueue<E>(int initialCapacity, Comparator<? super E> comparator)
// 实际使用
PriorityQueue<Integer> comparatorPQ = new PriorityQueue<>(11, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); // 逆序比较}
});5.集合和比较器构造
使用集合中的元素创建一个优先级队列，然后用指定的比较器来进行比较
PriorityQueue<E>(Collection<? extends E> c, Comparator<? super E> comparator)
// 实际使用
PriorityQueue<Integer> collectionWithComparatorPQ = new PriorityQueue<>(list, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1); // 逆序比较}
});PriorityQueue的常用方法
| 方法 | 作用 |
| boolean offer(E e) | 插入元素，不能为空且可以比较 |
| int size() | 有效元素个数 |
| E peek() | 获取堆顶元素，为空返回null |
| E poll() | 删除堆顶元素，为空返回null |
| boolean isEmpty() | 检查优先级队列是否为空 |
| void clear() | 检查队列是否为空 |
PriorityQueue的模拟实现
import java.util.Comparator;public class MyPriorityQueue {private int[] arr;private int usedSize;private Comparator<Integer> comparator;public MyPriorityQueue(int initialCapacity, Comparator<Integer> comparator) {this.arr = new int[initialCapacity];this.usedSize = 0;this.comparator = comparator;}public boolean isFull() {return usedSize == arr.length;}public boolean isEmpty() {return usedSize == 0;}public void offer(int val) {if (isFull()) {resize();}arr[usedSize] = val;heapInsert(usedSize);usedSize++;}public int poll() {if (isEmpty()) {throw new IllegalStateException("Priority queue is empty.");}int ret = arr[0];swap(0, usedSize - 1);usedSize--;heapify(0, usedSize);return ret;}private void heapify(int i, int size) {int left = i * 2 + 1;while (left < size) {int best = (left + 1 < size) && comparator.compare(arr[left + 1], arr[left]) > 0 ? left + 1 : left;best = comparator.compare(arr[best], arr[i]) > 0 ? best : i;if (best == i) {break;}swap(best, i);i = best;left = i * 2 + 1;}}private void heapInsert(int i) {while (i > 0 && comparator.compare(arr[i], arr[(i - 1) / 2]) > 0) {swap(i, (i - 1) / 2);i = (i - 1) / 2;}}private void swap(int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private void resize() {int[] newArray = new int[arr.length * 2];System.arraycopy(arr, 0, newArray, 0, arr.length);arr = newArray;}// 自定义 reverseOrder 方法public static Comparator<Integer> reverseOrder() {return (o1, o2) -> o2.compareTo(o1);}public static void main(String[] args) {// 创建大根堆System.out.println("大根堆：");MyPriorityQueue maxHeap = new MyPriorityQueue(10, reverseOrder());maxHeap.offer(5);maxHeap.offer(3);maxHeap.offer(8);System.out.println(maxHeap.poll());System.out.println(maxHeap.poll());System.out.println(maxHeap.poll());System.out.println("====================================");// 创建小根堆System.out.println("小根堆：");MyPriorityQueue minHeap = new MyPriorityQueue(10, Comparator.naturalOrder());minHeap.offer(5);minHeap.offer(3);minHeap.offer(8);System.out.println(minHeap.poll());System.out.println(minHeap.poll());System.out.println(minHeap.poll());}
}
