优先级队列（堆）

栈 队列https://blog.csdn.net/2401_83837907/article/details/147976747?spm1001.2014.3001.5501一.优先级队列的模拟实现》层序遍历存储小根堆跟都比左右子树小大根堆根都比左右子树大1.堆的存储方式堆是⼀棵完全⼆叉树因此可以层序的规则采⽤顺序的⽅式来⾼效存储(注意对于⾮完全⼆叉树则不适合使⽤顺序⽅式进⾏存储因为为了能够还原⼆叉树空间中必须要存储空节点就会导致空间利⽤率⽐较低。)将元素存储到数组中后可以对树进⾏还原。假设i为节点在数组中的下标则有• 如果i为0则i表⽰的节点为根节点否则i节点的双亲节点为(i-1)/2• 如果2*i1⼩于节点个数则节点i的左孩⼦下标为2*i1否则没有左孩⼦• 如果2*i2⼩于节点个数则节点i的右孩⼦下标为2*i2否则没有右孩⼦2.堆的创建大根堆依此再向下问题每棵子树结束的位置不固定》usedSize(堆中当前元素的个数public class MaxHeap { // 存储堆元素的数组 private int[] elem; // 堆中当前元素的个数有效长度 private int usedSize; // 构造函数初始化堆数组 public MaxHeap(int capacity) { //capacity 是堆底层数组的初始容量用来提前分配数组的大小 this.elem new int[capacity]; this.usedSize 0; } // 建堆把一个普通数组变成堆 public void createHeap(int[] array) { // 把数组拷贝到堆里 for (int i 0; i array.length; i) { this.elem[i] array[i]; } this.usedSize array.length; // parent 的入口从【最后一个非叶子节点】开始向下调整 for (int i (usedSize - 1 - 1) / 2; i 0; i--) { siftDown(i, usedSize); } } /** * 堆的向下调整大顶堆 * param parent 要调整的父节点下标 * param usedSize 堆的有效长度防止越界 */ private void siftDown(int parent, int usedSize) { // 1. 先得到左孩子的下标完全二叉树左孩子一定是 2*parent1 int child 2 * parent 1; // 循环条件孩子下标在堆的有效范围内 while (child usedSize) { // 2. 左右孩子比较让child指向值更大的那个孩子 // 条件右孩子存在child1 usedSize且左孩子值 右孩子值 if (child 1 usedSize elem[child] elem[child 1]) { child; // child指向右孩子更大的那个 } // 3. 用最大的孩子和父节点比较 if (elem[child] elem[parent]) { // 孩子值 父节点值交换两者 swap(elem, child, parent); // 父节点下沉到孩子位置继续向下调整 parent child; child 2 * parent 1; // 计算新父节点的左孩子 } else { // 孩子值 ≤ 父节点值已经满足大顶堆性质直接结束 break; } } } //交换数组中两个下标的元素 private void swap(int[] array, int i, int j) { int temp array[i]; array[i] array[j]; array[j] temp; }小根堆逻辑一样 只改,符号public class MinHeap { private int[] elem; private int usedSize; public MinHeap(int capacity) { this.elem new int[capacity]; this.usedSize 0; } // 建堆 public void createHeap(int[] array) { for (int i 0; i array.length; i) { this.elem[i] array[i]; } usedSize array.length; // 入口 parent最后一个非叶子节点 for (int i (usedSize - 2) / 2; i 0; i--) { siftDown(i, usedSize); } } // 小顶堆 向下调整 private void siftDown(int parent, int len) { int child 2 * parent 1; while (child len) { // 找 更小 的孩子 if (child 1 len elem[child] elem[child 1]) { child; } // 孩子 父亲 → 交换 if (elem[child] elem[parent]) { swap(child, parent); parent child; child 2 * parent 1; } else { break; } } } private void swap(int i, int j) { int tmp elem[i]; elem[i] elem[j]; elem[j] tmp; } }建堆的时间复杂度此处为了简化使⽤满⼆叉树来证明(时间复杂度看的就是近似值多⼏个节点不影响最终结果)3.堆的插入与删除1堆的插入/** * 堆的向上调整用于插入元素 * param child 要调整的孩子节点下标 */ private void siftUp(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; } } } /** * 向大顶堆中插入元素 * param val 待插入的值 * return 插入成功返回true满了返回false */ public boolean offer(int val) { // 自动扩容 if (usedSize elem.length) { // 新容量 原来的 2 倍 int newCapacity elem.length * 2; // 拷贝数组 elem Arrays.copyOf(elem, newCapacity); } // 放入最后位置 elem[usedSize] val; siftUp(usedSize); usedSize; return true; }2堆的删除// 删除堆顶 public int poll() { if (usedSize 0) { throw new RuntimeException(堆为空); } swap(elem, 0, usedSize - 1); usedSize--; siftDown(0, usedSize); return elem[usedSize]; }堆操作调整方式说明建堆向下调整siftDown从最后一个非叶子节点往前对非叶子节点执行删除堆顶向下调整siftDown仅对堆顶执行一次插入元素向上调整siftUp对新插入的末尾元素执行堆排序向下调整siftDown每次取堆顶后对堆顶执行一次4.用堆模拟实现优先级队列import java.util.Arrays; public class MaxHeap { // 存储堆元素的数组 private int[] elem; // 堆中当前元素的个数有效长度 private int usedSize; // 默认初始容量 private static final int DEFAULT_CAPACITY 10; // 构造函数使用默认容量 public MaxHeap() { this.elem new int[DEFAULT_CAPACITY]; this.usedSize 0; } // 构造函数初始化堆数组 public MaxHeap(int capacity) { if (capacity 1) { capacity DEFAULT_CAPACITY; } this.elem new int[capacity]; this.usedSize 0; } /** * 堆的向下调整大顶堆 * param parent 要调整的父节点下标 * param usedSize 堆的有效长度防止越界 */ private void siftDown(int parent, int usedSize) { // 1. 先得到左孩子的下标 int child 2 * parent 1; // 循环条件孩子下标在堆的有效范围内 while (child usedSize) { // 2. 找更大的孩子 if (child 1 usedSize elem[child] elem[child 1]) { child; } // 3. 孩子 父亲交换 if (elem[child] elem[parent]) { swap(elem, child, parent); parent child; child 2 * parent 1; } else { break; } } } /** * 交换数组中两个下标的元素 */ private void swap(int[] array, int i, int j) { int temp array[i]; array[i] array[j]; array[j] temp; } // 建堆 public void createHeap(int[] array) { // 扩容到足够大 if (array.length elem.length) { elem Arrays.copyOf(elem, array.length * 2); } System.arraycopy(array, 0, elem, 0, array.length); usedSize array.length; // 从最后一个非叶子节点开始调整 for (int i (usedSize - 1 - 1) / 2; i 0; i--) { siftDown(i, usedSize); } } // 向上调整插入用 private void siftUp(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; } } } // ✔ 扩容 插入 public boolean offer(int val) { // 自动扩容 if (usedSize elem.length) { // 新容量 原来的 2 倍 int newCapacity elem.length * 2; // 拷贝数组 elem Arrays.copyOf(elem, newCapacity); } // 放入最后位置 elem[usedSize] val; siftUp(usedSize); usedSize; return true; } // 删除堆顶 public int poll() { if (usedSize 0) { throw new RuntimeException(堆为空); } swap(elem, 0, usedSize - 1); usedSize--; siftDown(0, usedSize); return elem[usedSize]; } // 获取堆顶 public int peek() { if (usedSize 0) { throw new RuntimeException(堆为空); } return elem[0]; } // 获取当前元素数量 public int size() { return usedSize; } }二.PriorityQueue默认小根堆常用接口介绍1.PriorityQueue中放置的元素必须要能够⽐较⼤⼩不能插⼊⽆法⽐较⼤⼩的对象否则会抛出 ClassCastException异常2. 不能插⼊null对象否则会抛出NullPointerException3. 没有容量限制可以插⼊任意多个元素其内部可以⾃动扩容4. 插⼊和删除元素的时间复杂度为O(log₂n)5. PriorityQueue底层使⽤了堆数据结构1. 优先级队列的构造注意默认情况下PriorityQueue队列是⼩堆如果需要⼤堆需要⽤⼾提供⽐较器class IntCmp implements ComparatorInteger { Override public int compare(Integer o1, Integer o2) { return o2 - o1; // 关键在这里 //return o1 - o2 → 默认小顶堆升序 //return o2 - o1 → 大顶堆降序 } } public static void main(String[] args) { // 传入比较器 → 变成大顶堆 PriorityQueueInteger p new PriorityQueue(new IntCmp()); p.offer(4); p.offer(3); p.offer(2); p.offer(1); p.offer(5); System.out.println(p.peek());//5 }或者简写成不用写类PriorityQueueInteger pq new PriorityQueue((a, b) - b - a);2. 插⼊/删除/获取优先级最⾼的元素优先级队列的扩容说明• 如果容量⼩于64时是按照oldCapacity的2倍⽅式扩容的• 如果容量⼤于等于64是按照oldCapacity的1.5倍⽅式扩容的• 如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进⾏扩容3.top-k问题最⼩的K个数--利用堆class Solution { public int[] smallestK(int[] arr, int k) { int[] resnew int[k]; PriorityQueueInteger pqnew PriorityQueue(); for(int i0;iarr.length;i){ pq.offer(arr[i]); } for(int i0;ik;i){ res[i]pq.poll(); } return res; } }对于Top-K问题能想到的最简单直接的⽅式就是排序但是如果数据量⾮常⼤排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决基本思路如下1. ⽤数据集合中前K个元素来建堆前k个最⼤的元素则建⼩堆 ◦前k个最⼩的元素则建⼤堆2. ⽤剩余的N-K个元素依次与堆顶元素来⽐较不满⾜则替换堆顶元素 将剩余N-K个元素依次与堆顶元素⽐完之后堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素class Solution { public int[] smallestK(int[] arr, int k) { int[] res new int[k]; // 找最大 K 个 → 小顶堆 PriorityQueueInteger pq new PriorityQueue(); // 1. 前 k 个先入堆 for (int i 0; i k; i) { pq.offer(arr[i]); } // 2. 剩余元素依次和堆顶比较 for (int i k; i arr.length; i) { if (arr[i] pq.peek()) { // 比堆顶大就替换 pq.poll(); pq.offer(arr[i]); } } // 堆里就是最大 k 个 for (int i 0; i k; i) { res[i] pq.poll(); } return res; } }class Solution { public int[] smallestK(int[] arr, int k) { int[] res new int[k]; // 找最小 K 个 → 大顶堆 PriorityQueueInteger pq new PriorityQueue((a, b) - b - a); // 1. 前 k 个先入堆 for (int i 0; i k; i) { pq.offer(arr[i]); } // 2. 剩余元素依次比较 for (int i k; i arr.length; i) { if (arr[i] pq.peek()) { // 比堆顶小替换 pq.poll(); pq.offer(arr[i]); } } for (int i 0; i k; i) { res[i] pq.poll(); } return res; } }