数据结构之优先级队列(堆)及top-k问题讲解（一）+https://developer.aliyun.com/article/1413566
2. PriorityQueue常用接口介绍
1.构造方法
1.1不含参的构造方法
// 不含参的构造方法 public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } // 默认容量是11 private static final int DEFAULT_INITIAL_CAPACITY = 11;
1.2 指定容量的构造方法
// 指定容量的构造方法 public PriorityQueue(int initialCapacity) { this(initialCapacity, null); }
1.3指定容量 并接受比较器的构造方法（最核心的一个构造方法）
// 指定容量 并接受比较器的构造方法 public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility // 如果初始容量<1 就抛出异常 但实际上源码中也说了 <1这个条件并不是必需的 只不过是为了和1.5保持一致设置的条件 if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }
1.4利用其他集合创建一个优先级队列
只要实现了Collection的集合都能作为参数参与创建一个优先级队列
PriorityQueue(Collection<? extends E> c) 用一个集合来创建优先级队列
List<Integer> list = new ArrayList<>(); list.add(1); list.add(12); list.add(13); PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(list); System.out.println(priorityQueue.toString());// 输出1 12 13
2.PriorityQueue的扩容机制
PriorityQueue的存储结构是顺序表，在不断添加数据的时候涉及到扩容问题，下面来研究一下PriorityQueue中是如何进行扩容的
先来看offer对应的源码
public boolean offer(E e) { // 为空 直接抛出异常 不能插入空指针 if (e == null) throw new NullPointerException(); modCount++; int i = size; // 进行扩容 if (i >= queue.length) // grow方法内部是扩容的机制 grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else // 向上调整 siftUp(i, e); return true; }
接下来看grow方法的实现
3.如何实现大根堆
PriorityQueue默认是小根堆，想要实现大根堆则需要重新构建比较逻辑，使用Comparator接口，下面以整数的比较为例实现大根堆
1.方法一：直接构造一个比较器
// 构造比较器 实现大根堆 class IntCmp implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } } PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp()); priorityQueue.offer(1); priorityQueue.offer(2); priorityQueue.offer(33); priorityQueue.offer(44); priorityQueue.offer(55); System.out.println(priorityQueue.poll());// 输出55
2.方法二：使用匿名内部类
// 使用匿名内部类 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); priorityQueue.offer(1); priorityQueue.offer(2); priorityQueue.offer(33); priorityQueue.offer(44); priorityQueue.offer(55); System.out.println(priorityQueue.poll());// 输出55
3.方法三：使用lambda表达式(推荐)
// 使用lambda表达式 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>( (o1,o2) ->{return o2.compareTo(o1);} ); priorityQueue.offer(1); priorityQueue.offer(2); priorityQueue.offer(33); priorityQueue.offer(44); priorityQueue.offer(55); System.out.println(priorityQueue.poll());// 输出55
四.重点：top-k问题的三种解决方法
https://leetcode.cn/problems/smallest-k-lcci/description/
1.最简单的思路：对数组进行排序
// 解法1 public int[] smallestK1(int[] arr, int k) { int[] ret = new int[k]; if(arr == null || k <= 0) return ret; Arrays.sort(arr); // 排序之后 arr从小到大排列完毕 for (int i = 0; i < k; i++) { ret[i] = arr[i]; } return ret; }
2.直接使用堆（优先级队列）的特性 创建小根堆 poll k次即可
// 解法2 public int[] smallestK2(int[] arr, int k) { int[] ret = new int[k]; if(arr == null || k <= 0) return ret; PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); for (int i = 0; i < arr.length; i++) { priorityQueue.offer(arr[i]); } for (int i = 0; i < k; i++) { ret[i] = priorityQueue.poll(); } return ret; }
3.建立一个k个结点的大根堆 再与数组剩余元素进行比较（重点掌握）
步骤:
- 先将前k个元素创建为大根堆(k 是因为我最后要返回k个元素)
- 将数组中剩余的元素依次去和堆顶元素进行比较，如果小于堆顶元素，插入堆中
- 返回容量为k的大根堆
// 解法3 效率最高的一种方法 创建一个具有k个结点的大根堆 // 注意 优先级队列默认是小根堆 要实现大根堆 需要先创建一个实现了Comparator接口的对象 class IntCmp implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } } public int[] smallestK(int[] arr, int k) { int[] ret = new int[k]; if(arr == null || k <= 0) return ret; // 创建一个具有k个结点的大根堆 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp()); for (int i = 0; i < k; i++) { // 将前k个元素做成大根堆 priorityQueue.offer(arr[i]); } for (int i = k; i < arr.length; i++) { // 去和栈顶元素比较 if (arr[i] < priorityQueue.peek()) { // 证明栈顶元素不是前k个最小的元素 要删除 priorityQueue.poll(); priorityQueue.offer(arr[i]); } } for (int i = 0; i < k; i++) { ret[i] = priorityQueue.poll(); } return ret; }
时间复杂度分析：
前两种方法对于数据量特别大的情况十分不友好！占用的内存太大
变式：
求数组中第k大/小元素
// 求数组中第k大/小元素 // 前k个元素存储到小根堆中 堆里存放最大的k个元素 以小根堆的形式存储 则堆头一定是第k大的元素 public int maxKestK(int[] arr, int k) { if(arr == null || k <= 0) { throw new ArrayEmptyException("不含有元素或k不合法"); } // 创建一个具有k个结点的大根堆 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); for (int i = 0; i < k; i++) { // 将前k个元素做成小根堆 priorityQueue.offer(arr[i]); } for (int i = k; i < arr.length; i++) { if (arr[i] > priorityQueue.peek()) { priorityQueue.poll(); priorityQueue.offer(arr[i]); } } return priorityQueue.poll(); }
五.堆排
堆排序即利用堆的思想进行排序，堆排序的过程可以分为两步
- 确定排序方式：升序--建立大根堆 降序--建立小根堆
- 利用堆删除的思想(向下调整进行堆排)
图解：
代码实现
// 堆排序 // 升序 从小到大 创建大根堆 // 降序 从大到小 创建小根堆 /** * 升序 调整为大根堆 堆首元素一定是最大的 * 交换堆首和堆尾元素 向下调整（不包含被调下去的最大元素） 使第二大的元素位于堆顶 * 重复上述操作 每次都是堆首元素和堆尾元素进行交换 */ public void headSort() { int end = usedSize-1; while(end > 0) { swap(0,end); shiftDown(0,end); end--; } } private void shiftDown(int parent, int usedSize) { int child = 2 * parent+1;// 得到左孩子的下标 while (child < usedSize) { // 首先要保证child是左右孩子最大元素的下标 if(child + 1 < usedSize && elem[child] < elem[child+1]) { // 有右孩子 且右孩子的值比左孩子大 child++; } // 此时child就是值最大孩子的下标 if(elem[child] > elem[parent]) { swap(child,parent); parent = child; child = 2 * parent+1; }else { break; } } }
总结：
堆排时要选择好排序的顺序，如果是升序排序就创建大根堆，如果是降序排序就是用小根堆
以升序排序为例，创建一个大根堆存储数据，再不断交换堆顶和堆尾元素(此时一定是最大元素放到堆尾，最小元素放到堆顶)，再进行向下调整，向下调整的数据范围并不报错刚刚被挪动到堆尾的元素，使整个堆仍然保持大根堆的性质，这样最大的元素就被移动到最后，依次操作，每次都可以把当前数据范围内的最大元素移动到最后，最后创建出的堆中存储的数据就是升序排序的
这种"逆向思维"在堆中很常见，想让堆顶是最小的元素，就先创建大根堆，再不断地挪动数据，向下调整
