一、优先级队列
1.1 概念
前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
二、优先级队列的模拟实现
在JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。
2.1 堆的概念
如果有一个关键码的集合K={k0,k1,k2,......,kn-1},把它的所有元素按玩全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki<=K2i+1&&Ki<=K2i+2(Ki>K2i+1且Ki>=K2i+2)i=0,1,2...,则称为小堆（或大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：1.堆中的某个节点的值总是不大于或不小于其父节点的值；
2.堆总是一棵完全二叉树。
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
假设i为节点在数组中的下标，则有：
1.如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为（i-1)/2
2.如果2*i+1小于节点个数，则节点i的左孩子下标为2*i+1,否则没有左孩子
3.如果2*i+2小于节点个数，则节点i的右孩子下标为2*i+2,否则没有右孩子
2.2 堆的创建
2.2.1堆向下调整
对于集合{27,15,19,18,28,34,65,49,25,37}中的数据，如果将其创建成堆呢？
观察上图后发现，根节点的左右子树已经完全满足堆的性质，因此只需要将根节点向下调整即可。
向下过程（以小堆为例）：
1.让parent标记需要调整的节点，child标记parent的左孩子（注意：parent如果有左孩子一定是先有左孩子）
2.如果parent的左孩子存在，即：child<size,进行以下操作，直到parent的左孩子不存在
（1）parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记
（2）将parent与较小的孩子child比较，如果：
· parent小于较小的孩子child，调整结束
·否则：交换parent与较小的孩子child，交换完成后，parent中较大的元素向下移动，可能导 子树不满足堆的性质，因此需要继续向下调整，即parent=child；child=parent*2+1；然后 继续2。
public void shiftDown(int []array,int parent){ int child=parent*2+1; int size=array.length-1; while (child<=size){ if(child+1<=size){ child=array[child]<array[child+1]?child:child+1; } if(array[child]<array[parent]){ swap(array,child,parent); parent=child; child=parent*2+1; }else { break; } } } public void swap(int []array,int child,int parent){ int tmp=array[child]; array[child]=array[parent]; array[parent]=tmp; }
注意：在调整以parent为跟二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
时间复杂度分析：最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O（log₂n)
2.2.2 建堆的时间复杂度
代码：
public void creatHeap(int []array){ int root=(array.length-1-1)/2; for (;root>=0;root--){ shiftDown(array,root); } }
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处是为了简化使用二叉树来证明（时间复杂度本来看的就是近似值，多几个节点不影响最终结果）：
因此：建堆的时间复杂度为O(N)。
2.3 堆的插入与删除
2.3.1 堆的插入
堆的插入总共需要两个步骤：
1.先将元素放入地层空间中（注意：空间不够时需要扩容）
2.将最后插入的节点向上调整，知道满足堆的性质
public boolean isFull() { return usedSize == elem.length; } public void offer(int val) { if (isFull()) { elem=Arrays.copyOf(elem, elem.length * 2); } int child = usedSize; usedSize++; elem[child] = val; int parent = (child - 1) / 2; while (child > 0) { if (elem[child] < elem[parent]) { int tmp = elem[parent]; elem[parent] = elem[child]; elem[child] = tmp; child=parent; parent=(child-1)/2; }else { break; } } }
2.3.2 堆的删除
注意：堆的删除一定是堆顶元素。具体如下：
1. 将堆顶元素与堆中最后一个元素交换
2.将堆中有效数据个数减少一个
3.对堆顶元素进行向下调整
三.常用接口介绍
3.1 PriorityQueue的特性
Java集合框架提供了PriorityQueue和PriorityBlockingQueue两种优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
1.使用时必须导入PriorityQueue所在包，即：
import java.util.PriorityQueue;
2.PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
3.不能插入null对象，否则会抛出NullPointerException
4.没有容量限制，可以插入任意多个元素，其内容可以自动扩容
5.插入和删除元素的时间复杂度为O（log₂N）（插入采用向上调整法，删除采用向下调整法）
6.PriorityQueue底层使用了堆数据结构
7.PriorityQueue默认情况下是小堆——即每次获取到的元素都是最小的元素
3.2 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 code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
扩容说明：
1.如果容量小于64时，是按照oldCapacity的2倍方式扩容的
2.如果容量大于等于64时，是按照oldCapacity的1.5倍方式扩容的
3.如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容的。
3.3 PriorityQueue常用接口介绍
1.优先级队列构造器
注：无论调用哪个构造器，最后都会调用含有两个参数的构造器。
注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
3.4 oj练习
题解：可以先将前k个元素建成最大堆，将剩余元素和堆顶元素一一比较，若小于堆顶元素，先抛出堆顶元素，再将数组元素添加进去。
class NumComparator implements Comparator<Integer>{ @Override public int compare(Integer o1,Integer o2){ return o2-o1; } } class Solution { public int[] smallestK(int[] arr, int k) { NumComparator numComparator=new NumComparator(); int []ret=new int[k]; if(k==0||arr==null){ return ret; } PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(numComparator); for(int i=0;i<k;i++){ priorityQueue.offer(arr[i]); } for(int i=k;i<arr.length;i++){ if(arr[i]<priorityQueue.peek()){ priorityQueue.poll(); priorityQueue.offer(arr[i]); } } for(int i=0;i<k;i++){ ret[i]=priorityQueue.poll(); } return ret; } }
ps:求前k个最小元素，建大堆，求前k个最大元素，建小堆。
四、比较器Comparator
在优先级队列排序引用类型队列时，有两种比较方式如下：
1.引用类型继承comparable接口，并且实现了接口中的compaTo方法。
2.在构造优先级队列时，传递一个comparator比较器。
private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }
//年龄比较器 class AgeComparator implements Comparator<Student>{ @Override public int compare(Student o1, Student o2) { return (o1.age-o2.age); } } //名字比较器 class NameComparator implements Comparator<Student>{ @Override public int compare(Student o1, Student o2) { return o1.name.compareTo(o2.name); } } //student本身继承Comparable接口，重写comparTo方法 class Student implements Comparable<Student> { public String name; public int age; public Student(){ } public Student(int age,String name){ this.name=name; this.age=age; } @Override public int compareTo(Student o) { return this.name.compareTo(o.name); } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } }
此时便可根据自己的需求，通过重写compareTo方法或传入比较器来创建大小堆。
