从生活中的 VIP 通道到 Java 优先级队列完全指南在计算机科学的世界里数据结构往往来源于现实生活。今天我们要聊的主角——优先级队列 (Priority Queue)就是一个非常接地气且高效的工具。一、 什么是优先级队列通俗易懂的例子我们都知道普通的队列 (Queue) 是“先来后到”FIFO先进先出。比如在超市结账谁先排队谁就先买单。但在很多场景下绝对的公平反而不合理。生活中的例子医院急诊室假设急诊室有一个排队名单。如果只是按照先来后到的顺序前面排了 10 个感冒发烧的病人这时突然送来一个突发心脏病的患者。医生绝对不可能对他说“请去后面排队”。心脏病患者的优先级最高必须立刻插队处理。机场登机/高铁进站航空公司有 VIP 休息室和优先登机通道。哪怕头等舱乘客是最后到的他们依然可以最先登机。优先级队列就是这样一种数据结构无论元素加入队列的先后顺序如何每次出队的永远是优先级最高的元素。二、 优先级队列的基石堆 (Heap)在 Java 中PriorityQueue的底层是通过堆 (Heap)来实现的。堆本质上是一棵完全二叉树但它在物理存储上使用的是数组。最大堆 (Max Heap)父节点的值永远大于或等于其子节点的值。根节点就是全局最大值。最小堆 (Min Heap)父节点的值永远小于或等于其子节点的值。根节点就是全局最小值。 数组下标的数学魔法如果一个节点在数组中的索引是 $i$那么它的左孩子索引是 $2i 1$它的右孩子索引是 $2i 2$它的父节点索引是 $(i - 1) / 2$Java 实现最大堆与最小堆在 Java 中PriorityQueue默认实现的是最小堆。我们可以通过传入自定义的比较器 (Comparator) 轻松将其变成最大堆。Javaimport java.util.PriorityQueue; import java.util.Collections; public class HeapExample { public static void main(String[] args) { // 1. 默认最小堆 (Min Heap) PriorityQueueInteger minHeap new PriorityQueue(); minHeap.offer(5); minHeap.offer(1); minHeap.offer(8); System.out.println(最小堆出队顺序:); while (!minHeap.isEmpty()) { System.out.print(minHeap.poll() ); // 输出: 1 5 8 } System.out.println(\n-------------------); // 2. 自定义最大堆 (Max Heap) // 使用 Collections.reverseOrder() 改变优先级规则 PriorityQueueInteger maxHeap new PriorityQueue(Collections.reverseOrder()); maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(8); System.out.println(最大堆出队顺序:); while (!maxHeap.isEmpty()) { System.out.print(maxHeap.poll() ); // 输出: 8 5 1 } } }三、 算法进阶堆排序 (Heap Sort)堆排序是一种非常优秀的原地排序算法时间复杂度为 $O(N \log N)$空间复杂度仅为 $O(1)$。核心思想以升序排序为例需要使用最大堆将无序数组构建成一个最大堆此时数组的首元素arr[0]就是最大值。将堆顶元素最大值与数组末尾元素交换将最大值“沉”到数组尾部。将剩余的元素重新调整为最大堆范围减 1重复上述步骤直到整个数组有序。具体实现Javaimport java.util.Arrays; public class HeapSort { public static void heapSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 1. 构建最大堆 (从最后一个非叶子节点开始向下调整) for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 2. 依次取出堆顶元素移到数组末尾 for (int i n - 1; i 0; i--) { // 将当前最大的根节点移到末尾 swap(arr, 0, i); // 对剩下的 i 个元素重新调整为最大堆 heapify(arr, i, 0); } } // 将以 i 为根的子树调整为最大堆 private static void heapify(int[] arr, int n, int i) { int largest i; // 初始化最大值为根节点 int left 2 * i 1; int right 2 * i 2; // 如果左子节点大于根节点 if (left n arr[left] arr[largest]) { largest left; } // 如果右子节点大于目前的最大值 if (right n arr[right] arr[largest]) { largest right; } // 如果最大值不是根节点交换并递归调整 if (largest ! i) { swap(arr, i, largest); heapify(arr, n, largest); } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {12, 11, 13, 5, 6, 7}; heapSort(arr); System.out.println(堆排序后的数组: Arrays.toString(arr)); // 输出: [5, 6, 7, 11, 12, 13] } }四、 经典面试题Top K 问题问题描述在海量数据中找出最大的 $K$ 个数。思路解析不要对所有数据进行排序代价太大我们只需要维护一个容量为 $K$ 的最小堆。先将前 $K$ 个元素放入最小堆中。此时堆顶是这 $K$ 个数中最小的。遍历剩余的元素如果元素大于堆顶元素说明堆顶那个“菜鸡”不配留在 Top K 里。我们把堆顶踢出 (poll)将新元素加进去 (offer)。遍历结束后堆里剩下的就是最大的 $K$ 个数整体时间复杂度为 $O(N \log K)$非常适合处理海量数据流。具体实现Javaimport java.util.PriorityQueue; import java.util.Arrays; public class TopK { public static int[] findTopK(int[] nums, int k) { // 创建一个容量为 K 的最小堆 PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { // 如果堆还没满直接加 minHeap.offer(num); } else if (num minHeap.peek()) { // 如果满了且当前元素大于堆顶元素替换它 minHeap.poll(); minHeap.offer(num); } } // 将结果转换为数组 int[] result new int[k]; for (int i 0; i k; i) { result[i] minHeap.poll(); } return result; } public static void main(String[] args) { int[] nums {3, 2, 1, 5, 6, 4, 8, 9, 7}; int k 3; int[] topK findTopK(nums, k); System.out.println(最大的 k 个数是: Arrays.toString(topK)); // 输出可能顺序不同但元素一定是: [7, 8, 9] } }五、 源码探秘JavaPriorityQueue的扩容原理既然PriorityQueue底层是数组那数组满了怎么办它当然会自动扩容。翻开 JDK 的源码以 JDK 1.8 及其之后版本为例我们可以看到它的grow扩容方法。核心源码逻辑解析Java// JDK PriorityQueue 扩容核心逻辑简化 private void grow(int minCapacity) { int oldCapacity queue.length; // 双倍扩容还是 1.5 倍扩容看旧容量的大小 int newCapacity oldCapacity ((oldCapacity 64) ? (oldCapacity 2) : (oldCapacity 1)); // ... 后续处理内存溢出校验及数组拷贝 queue Arrays.copyOf(queue, newCapacity); }扩容规则总结当原容量比较小小于 64时扩容步长为oldCapacity 2。相当于扩大了一倍多一点近似于2 * oldCapacity 2。因为容量小的时候频繁扩容的概率高直接翻倍可以减少扩容次数。当原容量比较大大于等于 64时扩容步长为oldCapacity 1即原容量的一半。相当于扩大为原来的 1.5 倍。因为当容量已经很大时如果继续翻倍可能会导致大量的内存空间浪费甚至内存溢出 (OOM)所以扩容策略变得更加平缓。