前言
优先级队列就是在堆的基础上进行改造，那么什么是堆，又什么是优先级队列呢？
我们一起来看看吧！
目录
一、堆
堆就是堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是完全二叉树。
Java底层的堆是顺序表，按照层序遍历的规则存储数据。
堆分为小根堆和大根堆。
1.小根堆（又名最小堆）：
就是堆中某个节点的值总是不小于其父节点的值。
例如：
2.大根堆（又名最大堆）：
就是堆中某个节点的值总是不大于其父节点的值。
例如：
以创建最小堆为例，给出的数据顺序是： 5、3、6、7、4、2.
（一）堆的创建
首先，根据给出的数据顺序，创建如下二叉树：
从最后一个叶子节点开始调整（向上调整）：
时间复杂度是：O（n）
（二）堆的插入
假设要插入数据0：
如果在插入数据时，堆满扩容；调整为向上调整。
时间复杂度是：O(log n)
（三）堆的删除
堆的删除一定删除的是堆顶元素。
时间复杂度是：O(log n)
（四）模拟实现堆
代码：
import java.util.Arrays; import java.util.Comparator; class PriorityException extends RuntimeException{ public PriorityException(String s){ super(s); } } public class MyPriortyQueue implements Comparator<Integer> { public int[] elem; public int usedSize; public MyPriortyQueue(int k) { elem = new int[k]; } public MyPriortyQueue() { elem = new int[11]; } @Override public int compare(Integer o1,Integer o2) { return o2.compareTo(o1); } /** * 建堆 */ public void createHeap(int[] array) { for(int i = 0; i < array.length; i++){ elem[i] = array[i]; usedSize++; } for(int i = (usedSize-1-1)/2; i >= 0; i--){ shiftDown(i,usedSize-1); } } /** * 向下调整 * @param root 是每棵子树的根节点的下标 * @param len 是每棵子树调整结束的结束条件 * 向下调整的时间复杂度：O(logn) */ private void shiftDown(int root,int len) { int child = root*2+1; while(child < len){ if(child+1<len && compare(elem[child],elem[child+1])>0){ child++; } if(compare(elem[root],elem[child])>0){ int tmp = elem[root]; elem[root] = elem[child]; elem[child] = tmp; root = child; child = root*2+1; }else{ break; } } } /** * 入队：仍然要保持是大根堆 * @param val */ public void push(int val) { if(isEmpty()){ elem[0] = val; }else{ elem[usedSize] = val; } usedSize++; shiftUp(usedSize-1); } /** * 向上调整 * 默认除了需要调整的地方外，其余都是已经调整好了的 */ private void shiftUp(int child) { int parent = (child-1)/2; while(child > 0){ if(compare(elem[parent],elem[child])>0){ int tmp = elem[parent]; elem[parent] = elem[child]; elem[child] = tmp; child = parent; parent = (child-1)/2; }else{ break; } } } public boolean isFull() { return usedSize == elem.length; } /** * 出队【删除】：每次删除的都是优先级高的元素 * 仍然要保持是大根堆 */ public void pollHeap() throws PriorityException{ if(isEmpty()){ throw new PriorityException("pollHeap::队列无元素，删除失败"); } elem[0] = elem[usedSize-1]; usedSize--; shiftDown(0, usedSize-1); } public boolean isEmpty() { return usedSize == 0; } /** * 获取堆顶元素 * @return */ public int peekHeap() throws PriorityException{ if(isEmpty()){ throw new PriorityException("peekEmpty::队列无元素，获取失败"); } return elem[0]; } public static void main(String[] args) { MyPriortyQueue p = new MyPriortyQueue(); int[] arr = {2,4,2,5,7,9,5,3}; p.createHeap(arr); System.out.println("+=========创建一个堆========+"); System.out.println(Arrays.toString(p.elem)); p.push(10); System.out.println("+=========入一个值========+"); System.out.println(Arrays.toString(p.elem)); System.out.println("+=========输出堆顶========+"); System.out.println(p.peekHeap()); p.pollHeap(); System.out.println("+=========删除堆顶=======+"); System.out.println(Arrays.toString(p.elem)); } }
代码链接在GitHub：堆_练习模拟实现2 · Yjun6/DataStructrue@98faae5 (github.com)
二、优先级队列
PriorityQueue<Integer> p = new PriorityQueue<>();
（一）常用方法：
| boolean offer(E e) | 插入元素e,成功插入返回true;会自动扩容；如果e为空，会抛出异常 |
| E peek() | 获取优先级队列最高的元素；若队列为空，返回null |
| E poll() | 移除优先级队列最高的元素；若队列为空，返回null |
| int size() | 获取有效元素个数 |
| void clear() | 清空 |
| boolean isEmpty() | 判断是否为空 |
关于创建优先级队列的方法：
| PriorityQueue() | 初始容量为11，默认无比较器 |
| PriorityQueue(int k) | 初始容量为k，k>0 |
| PriorityQueue(Collection<? extend E> c) | 用一个集合创建优先级队列 |
优先级队列扩容说明：
- 如果容量小于64，按照2倍扩容；
- 如果容量大于等于64，按照1.5倍扩容；
- 如果容量超过 MAX_ARRAY_SIZE，按照 MAX_ARRAY_SIZE 进行扩容。
（二）常考点
求前k个最大值、前k个最小值、第k个最大值、第k个最小值……
面试题 17.14. 最小K个数 - 力扣（Leetcode）
代码：
class Solution { public int[] smallestK(int[] arr, int k) { if(arr == null || k == 0) return new int[k]; Comp comp = new Comp(); PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(comp);//求大根堆 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]); } } int[] str = new int[priorityQueue.size()]; for(int i = 0; i < str.length; i++){ str[i] = priorityQueue.poll(); } return str; } } class Comp implements Comparator<Integer> { @Override public int compare(Integer a, Integer b){ return b.compareTo(a); } }
结语
小编能力有限，欢迎大家指出错误哦~
这篇博客如果对你有帮助，给博主一个免费的点赞以示鼓励，欢迎各位🔎点赞👍评论收藏⭐，谢谢！！！
