🍁1. 优先级队列的概念
在之前已经了解过，队列是一种先进先出的数据结构，而优先级队列是一种抽象数据类型，其中每个元素都有一个优先级。与标准的队列不同，优先级队列中元素的顺序是根据其优先级来决定的，而不是按插入的顺序，优先级高的元素将优先出队。
JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。
🍁2. 堆的介绍
堆是一种特殊的完全二叉树结构，堆又可以分为大根堆和小根堆
大根堆：每个节点的值都大于或等于其子节点的值，也就是根节点是树中的最大值。
小根堆：每个节点的值都小于或等于其子节点的值，也就是根节点包含树中的最小值。
🍁3. 堆的模拟实现
底层通过数组来实现堆
public class MyHeap { public int[] elem; public int usedSize; public MyHeap(int[] elem) { this.elem = elem; } }
将元素存储在数组中后，如果孩子节点的下标为i，那么双亲节点的下标为（i - 1）/ 2
如果双亲节点的下标为 i ，那么左孩子的下标为 2*i+1，右孩子的下标为 2*i+2，如果左孩子或右孩子下标越界了就表示没有左孩子或右孩子
明白了节点怎么表示后就可以根据这些关系进行建堆了，
从最后一棵子树开始，依次往上调用向下调整
public void createHeap() { //最后一棵子树 for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) { siftDown(parent, this.usedSize); } }
🍁3.1 向下调整建堆
向上调整通常指的是在插入新元素到堆中后，为了确保堆的性质（父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）其子节点的值），对堆进行调整
以大根堆的创建为例：
通过双亲节点计算出左孩子节点的下标，如果左孩子存在，就继续判断右孩子是否存在，如果右孩子也存在并且右孩子大于左孩子，就把child的位置更新为右孩子，接着和双亲节点进行比较，如果比双亲节点大，就交换，以此循环调整
private void siftDown(int parent, int usedSize) { int child = parent * 2 + 1; while (child < usedSize) { //右孩子大于左孩子的情况，更新孩子节点 if (child + 1 < usedSize && elem[child] < elem[child + 1]) { child++; } if (elem[child] > elem[parent]) { int tmp = elem[parent]; elem[parent] = elem[child]; elem[child] = tmp; //往下更新双亲节点和孩子节点 parent = child; child = child * 2 + 1; } else { break; } } }
这个时间复杂度通过推导得出是一个O(n)的
🍁3.2 向上调整
给出一个孩子节点，再求出双亲节点，接着比较双亲节点和孩子节点，进行调整，这里的结束条件是双亲节点小于或等于0，意味着此时已经调整到了堆顶
还是以大根堆为例，由于大根堆要求的是双亲节点要大于孩子节点，所以无论是左孩子还是右孩子比双亲节点大，都需要交换，所以这里就不用区分左孩子还是右孩子了，都按照左孩子节点进行
private void siftUp(int child){ int parent = (child - 1) / 2; while(parent >= 0){ if(elem[child] > elem[parent]){ int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; child = parent; parent = (child - 1) / 2; }else{ break; } } }
向上调整的方法由于比向下调整多了最后一层的操作，所以时间复杂度为O(n + logn)
🍁3.3 插入
插入的思路就是先把元素放在最后，接着调用向上调整，依次把要插入的元素调整到适合的位置
public void offer(int val){ if(isFull()){ elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize] = val; //调用向上调整 siftUp(usedSize); usedSize++; } public boolean isFull(){ return usedSize == elem.length; }
🍁3.4 删除
思路：把根节点和最后一个节点交换，接着把usedSize--，这样就达到了删除的效果，并且此时只有根节点不满足大根堆的条件，只需要再次调用向下调整，就符合了大根堆
public int poll(){ if(isEmpty()){ throw new QueueEmptyException("队列为空"); } int val = elem[0]; //把根节点元素交换到末尾 swap(elem,0,usedSize-1); siftDown(0,usedSize-1); //usedSize--就表示已经删除了 usedSize--; return val; }
🍁3.5 获取堆顶元素
直接对堆顶元素进行返回即可
public int peek(){ if(isEmpty()){ throw new QueueEmptyException("队列为空"); } return elem[0]; }
🍁4. 堆的应用
🍁4.1 堆排序
将一组数据从小到大进行排序，使用到的是大根堆，大根堆的根节点肯定是最大的，然后把根节点和末尾元素交换，接着进行向下调整，然后新的根节点再和倒数第二个元素交换，以此类推，最终就可以实现从小到大排序的效果
public void heapSort(){ int end = usedSize - 1; while(end > 0){ swap(elem,0,end);//交换 siftDown(0,end);//调整 end--;//更新 } }
堆排序的时间复杂度是nlogn，如果加上创建堆，就是n + nlogn，依旧是nlogn
🍁4.2 top k 问题
topk 问题指的是求出数据集合中前k个最大或最小的元素
例如求出前k个最小的元素，会有以下几种方法：
1.整体进行排序，取出前k个元素
2.创建小根堆，拿出k个堆顶元素
3.把前k个元素创建为大根堆，遍历剩下的N-k个元素，和堆顶元素比较，如果比堆顶元素小，就删除堆顶元素，当前元素入堆，遍历完成后小根堆中的k个元素即为所求
第三种方法，当k很小时时间复杂度就趋近于o(n)，是比前面的两种高效的
来看一道力扣上的面试题：
class IntCmp implements Comparator<Integer>{ public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } } class Solution { public int[] smallestK(int[] arr, int k) { int[] res = new int[k]; if(arr == null || k == 0){ return res; } PriorityQueue<Integer> queue = new PriorityQueue<>(k, new IntCmp()); for (int i = 0; i < k; i++) { queue.offer(arr[i]); } for (int i = k; i < arr.length; i++) { if (arr[i] < queue.peek()) { queue.poll(); queue.offer(arr[i]); } } for (int i = k - 1; i >= 0; i--) { res[i] = queue.poll(); } return res; } }
🍁5. Java中PriorityQueue的使用
使用PriorityQueue时需要注意：
1. 放置的元素必须能够比较大小，不能插入无法比较大小的对象，否则会抛出异常
2. 不能插入null对象，否则会空指针异常
3. 插入和删除的时间复杂度为O(log ₂ n)
4. 默认情况下是小根堆
我们来演示一下这些构造方法
public class PriorityQueueDemo { public static void main(String[] args) { //创建一个默认容量的优先级队列 PriorityQueue<Integer> queue1 = new PriorityQueue<>(); //创建一个100容量的优先级队列 PriorityQueue<Integer> queue2 = new PriorityQueue<>(100); //传入ArrayList对象创建对象 ArrayList<Integer> arrayList = new ArrayList<>(); arrayList.add(3); arrayList.add(1); arrayList.add(2); PriorityQueue<Integer> queue3 = new PriorityQueue<>(arrayList); System.out.println(queue3); } }
很明显，最终的结果也是一个小根堆的形式，如果想要创建大根堆需要传入相应的比较器
class IntCmp implements Comparator<Integer>{ public int compare(Integer o1, Integer o2) { return o2.compareTo(o1);//Integer类型不能用 "-" 比较 } } public class PriorityQueueDemo { public static void main(String[] args) { //传入比较器对象 PriorityQueue<Integer> queue4 = new PriorityQueue<>(new IntCmp()); queue4.add(3); queue4.add(1); queue4.add(2); System.out.println(queue4); } }
此外，其他的方法和上面实现的一样
