优先级队列（堆）

栈 队列：https://blog.csdn.net/2401_83837907/article/details/147976747?spm=1001.2014.3001.5501

一.优先级队列的模拟实现

==》层序遍历存储

小根堆：跟都比左右子树小

大根堆：根都比左右子树大

1.堆的存储方式

堆是⼀棵完全⼆叉树，因此可以层序的规则采⽤顺序的⽅式来⾼效存储，

(注意：对于⾮完全⼆叉树，则不适合使⽤顺序⽅式进⾏存储，因为为了能够还原⼆叉树，空间中必须要存储空节点，就会导致空间利⽤率⽐较低。)

将元素存储到数组中后，可以对树进⾏还原。假设i为节点在数组中的下标，则有：

• 如果i为0，则i表⽰的节点为根节点，否则i节点的双亲节点为(i-1)/2

• 如果2*i+1⼩于节点个数，则节点i的左孩⼦下标为2*i+1，否则没有左孩⼦

• 如果2*i+2⼩于节点个数，则节点i的右孩⼦下标为2*i+2，否则没有右孩⼦

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*parent+1） int child = 2 * parent + 1; // 循环条件：孩子下标在堆的有效范围内 while (child < usedSize) { // 2. 左右孩子比较，让child指向值更大的那个孩子 // 条件：右孩子存在（child+1 < 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]; }

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对象，否则会抛出NullPointerException

3. 没有容量限制，可以插⼊任意多个元素，其内部可以⾃动扩容

4. 插⼊和删除元素的时间复杂度为O(log₂n)

5. PriorityQueue底层使⽤了堆数据结构

1. 优先级队列的构造

注意：默认情况下，PriorityQueue队列是⼩堆，如果需要⼤堆需要⽤⼾提供⽐较器

class IntCmp implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; // 👈 关键在这里 //return o1 - o2 → 默认小顶堆（升序） //return o2 - o1 → 大顶堆（降序） } } public static void main(String[] args) { // 传入比较器 → 变成大顶堆 PriorityQueue<Integer> 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 }

或者简写成：（不用写类）

PriorityQueue<Integer> 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[] res=new int[k]; PriorityQueue<Integer> pq=new PriorityQueue<>(); for(int i=0;i<arr.length;i++){ pq.offer(arr[i]); } for(int i=0;i<k;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 个 → 小顶堆 PriorityQueue<Integer> 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 个 → 大顶堆 PriorityQueue<Integer> 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; } }