优先级队列的概念
队列是一种先进先出的数据结构，但在一些情况下我们要优先处理一些情况，比如：正在手机上打游戏的时候，如果有来电，那么系统就应该处理打进来的电话。
在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
优先级队列的模拟实现
DK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。因此我们先来模拟堆的创建，插入与删除。
堆的创建
堆的创建代码：
//找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点,遇到一个节点就使用向下调整 public void creatHeap(int[] arr){ int root = (arr.length-2)/2; for (; root>=0 ; root--) { shiftDown(arr,root); } }
建堆的时间复杂度为O(N)
堆的向下调整代码（以创建大堆代码为例）：
public void shiftDown(int[] arr, int parent){ // child先标记parent的左孩子，因为parent可能右左没有右 int child = parent*2+1; int size = arr.length; while (child < size){ // 如果右孩子存在，找到左右孩子中较大的孩子,用child进行标记 if(child+1 < size && arr[child] < arr[child+1]){ child++; } // 如果双亲比其最大的孩子还小，则交换 if(arr[child]>parent){ int temp = arr[child]; arr[child] = arr[parent]; arr[parent] = temp; }else { break; } parent = child; child = (parent*2)+1; } }
堆的插入与删除
堆的插入
堆的插入总共需要两个步骤：
- 先将元素放入到底层空间中(注意：空间不够时需要扩容)
- 将最后新插入的节点向上调整，直到满足堆的性质
public void push(int val) { if(isFull()){ return; } //usedSize为堆中元素个数 elem[usedSize]=val; usedSize++; shiftUp(usedSize-1); }
向上调整：
private void shiftUp(int child){ // 找到child的双亲 int parent = (child-1)/2; while (parent >= 0){ if(arr[parent]>=arr[child]){ break; }else { // 将双亲与孩子节点进行交换 int temp = arr[parent]; arr[parent] = arr[child]; arr[child] = temp; child = parent; parent = (child-1)/2; } } }
堆的删除
堆的删除一定删除的是堆顶元素。具体如下：
- 将堆顶元素对堆中最后一个元素交换
- 将堆中有效数据个数减少一个
- 对堆顶元素进行向下调整
public void pollHeap() { if(isEmpty()){ return; } elem[0] = elem[usedSize-1]; usedSize--; shiftDown(0,usedSize); }
用堆模拟实现优先级队列
public class MyPriorityQueue { private int[] array = new int[100]; private int size = 0; //入队 public void offer(int e) { array[size++] = e; //向上调整 shiftUp(size - 1); } //出队 public int poll() { int oldValue = array[0]; array[0] = array[--size]; //向下调整 shiftDown(0); return oldValue; } //出堆首元素 public int peek() { return array[0]; } }
常见接口了解
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。
关于PriorityQueue的使用要注意：
- 使用时必须导入PriorityQueue所在的包
- PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
- 不能插入null对象，否则会抛出NullPointerException
- 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
- 插入和删除元素的时间复杂度为O（logN）
- PriorityQueue底层使用了堆数据结构
- PriorityQueue默认情况下是小堆-即每次获取到的元素都是最小的元素
PriorityQueue的几种常见构造方法
| 构造器 | 功能介绍 |
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常 |
| PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
我们可以使用优先级队列解决一些问题，例如TOPK问题：最大或者最小的前k个数据。
思路就是我们求最大的前k个数据，我们用数据的前k个数字建一个小堆，然后依次拿堆顶元素与剩下的数据进行比较，如果那个数据大于堆定元素就进行互换，直到遍历完剩下的数据，堆中k个数据就为最大的k个数据。堆顶元素就为第k大元素。
总结思路就是：
- 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
