1.优先级队列的模拟实现
1.1 优先级队列及堆的概念
在前边的文章中，我们介绍过队列这一数据结构【Queue——队列】,其是一种先入先出的数据结构，但是在一些常见中，如果队列中的元素带有优先级，就可能需要让优先级高的元素先出队列。
实际场景：我们在手机上刷剧时有人打进来电话，那么系统将会优先处理打进来的电话
在这种情况下，我们就有了优先级队列(Priority Queue ）这种数据结构，这种数据结构提供了两个基本操作，一是返回最高优先级对象，二是添加新的对象。
而PriorityQueue的底层使用了堆的数据结构，堆其实就是一棵完全二叉树，若该完全二叉树的每棵子树都是根结点最大叫做大根堆（否则就是小根堆）【也就是说堆中某个节点的值总是不大于或小于其父结点的值】。
1.2 堆的存储方式
堆是一棵完全二叉树，所以可以采用层序的规则来顺序高效存储元素。
如上图所示的完全二叉树，利用层序规则将其中元素顺序存储到数组中：
对于非完全二叉树，则不适用于该顺序方式进行存储，因为将会浪费掉一些空间来还原完全二叉树，将会导致其空间利用率较低。
在完全二叉树中，假设i为结点在数组中的下标，则有以下性质：
- 结点 i 的父结点为(i-1)/2
- 结点 i 的左孩子节点为2 * i+1，右孩子节点为2 * i+2
1.3 堆的创建
1.3.1 堆的创建与向下调整
我们以集合{27,15,19,18,28,34,65,49,25,37}中的数据为例，来将其创建成堆（以大顶堆为例）：
堆结构：
public class Heap { public int[] elem; public int usedSize;//当前堆中有效元素的个数 public Heap() { this.elem=new int[10]; } public void initArray(int[] array) { elem= Arrays.copyOf(array,array.length); usedSize=elem.length; } }
大顶堆需要满足条件为二叉树中每棵子树中根结点为最大值。
步骤：
1.确定最后一棵子树的根结点位置：
需要先找到最后一棵子树的最后一个节点的位置 ：len-1；
若该节点下标为i，则其父亲节点的下标为（i-1）/2,所以最后一棵子树的根结点为(len-1-1)/2。
2.下一棵子树的根结点为当前根结点-1
建堆：
/** * 建堆 * 时间复杂度：O(N) */ public void createHeap() { for (int parent = (usedSize-1-1); parent >=0 ; parent--) { shiftDown(parent,usedSize); //usedSize保证是所有子树的下标都不会比其大，也可比较用于所有子树的结束 } }
向下调整：
/** * 向下调整 * @param parent 每棵子树的根结点下标 * @param len 每棵子树的结束位置(usedSize) */ private void shiftDown(int parent,int len) { int child=2*parent+1; //len(usedSize)记录的是每棵子树的结束位置，只有当child<len时才需要做比较，然后向下调整 while (child<len) { //存在右孩子的情况下，比较左右孩子的大小，child记录较大值的下标 if(child+1<len&&elem[child]<elem[child+1]) { child++; } //此时child记录的是孩子中的较大值，再去与父节点进行比较 if(elem[child]>elem[parent]) { swap(elem,child,parent); //向下调整，让parent到child的位置，继续往下做比较 parent=child; child=2*parent+1; }else { //如果走到else，说明此时该子树符合大顶堆结构，不需要再做向下调整，直接跳出循环即可 break; } } } /** * 交换两结点 */ private void swap(int[]array,int i,int j) { int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
1.3.2 建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此：建堆的时间复杂度为O(N).
1.4 堆的插入与删除
1.4.1堆的插入
注：当将元素插入堆尾时，若空间不够，则需要扩容。
将最后新插入的节点向上调整，直到满足堆的性质需要向上调整，代码如下：
/** * 插入元素（入队） * @param x */ public void offer(int x) { if(isFull()) { elem=Arrays.copyOf(elem,elem.length*2); } this.elem[usedSize]=x; usedSize++; } public boolean isFull() { return usedSize==elem.length; }
/** * 向上调整 * @param child 子结点下标 */ private void shiftUp(int child) { //找到其父结点 int parent=(child-1)/2; //向上调整一直到根结点结束 while (child>0) { //判读子结点与父结点大小 if(elem[child]>elem[parent]) { swap(elem,child,parent); child=parent; parent=(child-1)/2; }else { //若不需要调整，则直接跳出循环 break; } } }
1.4.2堆的删除
/** * 删除元素（出队） * @return */ public int poll() { if(isEmpty()) { return -1; } int old=elem[0]; //交换堆顶与堆尾元素 swap(elem,0,usedSize-1); //删除堆尾元素 usedSize--; //将堆顶元素向下调整 shiftDown(0,usedSize); return old; } public boolean isEmpty() { return usedSize==0; }
总结：
堆的插入和删除元素的时间复杂度都是O（log2(N)）,也是树的高度；在向上调整或者向下调整的方法中可以知道，都是从最后一个结点开始调整，一直到根结点结束，若N为结点总个数，则进行log2(N)次基本操作。
练习：
答案：
1.A 2.C 3.C 4.C
题解：
1.堆为大顶堆或者小顶堆，其均为完全二叉树，将题目所给顺序排树即可得出是否为堆排序。最后选出答案A。
2.删除堆顶元素8，首先完成堆顶元素8和堆尾元素12的互换，然后堆顶元素的两个子结点15、10进行比较（第一次），较小结点10再与堆顶元素12比较（第二次），互换位置后，12还需要与16比较（第三次），共3次故选C。
3.将构建起的完全二叉树的所有子树做向下调整，得到答案C（该题目为大顶堆）
4.将堆顶元素与堆尾元素互换并将堆尾元素删除，然后将堆顶元素做向下调整得到如图堆示意图：
故选C。
2.常用接口介绍
2.1 PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
关于PriorityQueue的使用要注意：
1.使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
2.PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常（实现Comparable或者Comparator接口，指定比较方式）
3.不能插入null对象，否则会抛出NullPointerException
4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5.插入和删除元素的时间复杂度为O（log2(N)）
6.PriorityQueue底层使用了堆数据结构, 默认情况下是小堆—即每次获取到的元素都是最小的元素
2.2 PriorityQueue常用接口介绍
1.优先级队列的构造
| 构造器 | 功能介绍 |
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常 |
| PriorityQueue(Collection<?extends E> c) | 用一个集合来创建优先级队列 |
public static void main(String[] args) { //创建一个空的优先级队列，底层默认容量为11 PriorityQueue<Integer> q1=new PriorityQueue<>(); //创建一个空的优先级队列，底层容量为initialCapacity PriorityQueue<Integer> q2=new PriorityQueue<>(100); ArrayList<Integer> list=new ArrayList<>(); list.add(4); list.add(3); list.add(2); list.add(1); //用ArrayList对象来构造一个优先级队列的对象 PriorityQueue<Integer> q3=new PriorityQueue<>(list); }
默认情况下PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器：
public static void main(String[] args) { PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }); priorityQueue.offer(1); priorityQueue.offer(2); priorityQueue.offer(3); priorityQueue.offer(4); priorityQueue.offer(5); System.out.println(" "); }
2.插入/删除/获取优先级最高的元素
| 函数名 | 功能介绍 |
boolean offer(E e) |
插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度 O(Nlog2N)，注意：空间不够时候会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检测优先级队列是否为空，空返回true |
注意：下图为PriorityQueue的扩容源码
优先级队列的扩容说明：
- 如果容量小于64时，是按照oldCapacity的2倍方式扩容的
- 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
- 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容
3.PriorityQueue的应用
3.1 堆排序
堆排序即利用堆的思想来排序，让堆中的元素按照升序或者降序排布。
步骤：
1.建堆
升序建大堆 降序建小堆
2.利用堆删除思想来进行排序
以排升序为例，我们首先将元素建大堆，则堆顶元素为所有元素中的最大值，将堆顶元素与堆尾元素互换位置，则堆尾元素即为所有元素中的最大值。再让堆顶元素向下调整（有效位置-1，不排原堆尾元素），再让此时的堆尾元素与堆顶元素互换位置进行相同操作，这样就可以保证堆中元素顺序为升序。
注：红圈中的数字代表顺序
操作都是堆顶与堆尾元素互换后将堆顶元素向下调整，堆尾前移一个然后继续相同操作。
代码实现：
主要逻辑：
public void heapSort() { //堆尾位置 int end=usedSize-1; //一直相同操作直到堆顶 while (end>0) { //交换堆顶与堆尾元素 swap(elem,0,end); //将堆顶元素向下调整(传参end为向下调整结束位置，因为向下调整方法区间为<) shiftDown(0,end); end--; } }
以下代码在前边以及涉及到，这里再写一遍。
/** * 向下调整 * @param parent 每棵子树的根结点下标 * @param len 每棵子树的结束位置(usedSize) */ private void shiftDown(int parent,int len) { int child=2*parent+1; //len(usedSize)记录的是每棵子树的结束位置，只有当child<len时才需要做比较，然后向下调整 while (child<len) { //存在右孩子的情况下，比较左右孩子的大小，child记录较大值的下标 if(child+1<len&&elem[child]<elem[child+1]) { child++; } //此时child记录的是孩子中的较大值，再去与父节点进行比较 if(elem[child]>elem[parent]) { swap(elem,child,parent); //向下调整，让parent到child的位置，继续往下做比较 parent=child; child=2*parent+1; }else { //如果走到else，说明此时该子树符合大顶堆结构，不需要再做向下调整，直接跳出循环即可 break; } } } /** * 交换两结点 */ private void swap(int[]array,int i,int j) { int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
3.2 Top-k问题
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素
在我们了解到堆这个数据结构后很容易想到利用堆挨个弹出堆顶元素的方法来获得有序数组，也就解决了TOP-K问题，但是这种方法的时间复杂度为
O(N*log2N),时间复杂度太高，如果数据量较大的情况下，这种方法将不适用，所以我们有了下边这种优化的方法：
1.用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
2.用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
我们以数组{12，45，32，17，2，18，5，10}为例，求其前3大的元素。
1.先以前3个元素建小堆
这样堆顶元素就是前三个元素中的最小值。
2.将剩余的元素依次与堆顶元素进行比较，如果比堆顶元素大就替换
这样将所有元素比较并调整后，得到该小顶堆中的三个元素就是所有数组中前三大的元素。
替换的底层实现为先删除堆顶元素（将新堆顶元素做向下调整），再插入堆尾元素（并将堆尾元素做向上调整）。
与之类似的问题，若求第K大的元素，也是相同的方法，先以前K个元素建小堆，然后剩余元素依次与堆顶比较，最后得到小堆得堆顶元素即为第K大的元素。
总结：
求前k个最大的元素或者第K个最大的元素——建小堆
求前k个最小的元素或者第K个最小的元素——建大堆
对应OJ练习：【面试题 17.14. 最小K个数】
题意：
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
思路：在上边已经介绍过了。
代码：
class Solution { public int[] smallestK(int[] arr, int k) { int[]ret=new int[k]; if(k==0) return ret; /*求前K个最小的元素需要建大顶堆，所以需要让 优先级队列实现Comparator接口来重写排序方式。*/ PriorityQueue<Integer> q=new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }); //先将前K个元素入队 for (int i = 0; i < k; i++) { q.offer(arr[i]); } //将剩余的元素与堆顶元素比较并调整 for (int i = k; i < arr.length; i++) { if(q.peek()>arr[i]) { q.poll(); q.offer(arr[i]); } } //最后将队列中的元素存储到数组中返回数组即可。 for (int i = 0; i < k; i++) { ret[i]=q.poll(); } return ret; } }
