🚀 从生活中的 VIP 通道到 Java 优先级队列完全指南

在计算机科学的世界里，数据结构往往来源于现实生活。今天我们要聊的主角——优先级队列 (Priority Queue)，就是一个非常接地气且高效的工具。

一、 什么是优先级队列？（通俗易懂的例子）

我们都知道普通的队列 (Queue) 是“先来后到”（FIFO：先进先出）。比如在超市结账，谁先排队谁就先买单。但在很多场景下，绝对的公平反而不合理。

生活中的例子：

1. 医院急诊室： 假设急诊室有一个排队名单。如果只是按照先来后到的顺序，前面排了 10 个感冒发烧的病人，这时突然送来一个突发心脏病的患者。医生绝对不可能对他说：“请去后面排队”。心脏病患者的优先级最高，必须立刻插队处理。

2. 机场登机/高铁进站： 航空公司有 VIP 休息室和优先登机通道。哪怕头等舱乘客是最后到的，他们依然可以最先登机。

优先级队列就是这样一种数据结构：无论元素加入队列的先后顺序如何，每次出队的永远是优先级最高的元素。

二、 优先级队列的基石：堆 (Heap)

在 Java 中，PriorityQueue 的底层是通过堆 (Heap) 来实现的。堆本质上是一棵完全二叉树，但它在物理存储上使用的是数组。

• 最大堆 (Max Heap)： 父节点的值永远大于或等于其子节点的值。根节点就是全局最大值。

• 最小堆 (Min Heap)： 父节点的值永远小于或等于其子节点的值。根节点就是全局最小值。

💡 数组下标的数学魔法：

如果一个节点在数组中的索引是 $i$，那么：

• 它的左孩子索引是 $2i + 1$

• 它的右孩子索引是 $2i + 2$

• 它的父节点索引是 $(i - 1) / 2$

Java 实现：最大堆与最小堆

在 Java 中，PriorityQueue 默认实现的是最小堆。我们可以通过传入自定义的比较器 (Comparator) 轻松将其变成最大堆。

Java

import java.util.PriorityQueue;
import java.util.Collections;

public class HeapExample {
    public static void main(String[] args) {
        // 1. 默认：最小堆 (Min Heap)
        PriorityQueue<Integer> 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() 改变优先级规则
        PriorityQueue<Integer> 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)$。

核心思想（以升序排序为例，需要使用最大堆）：

1. 将无序数组构建成一个最大堆（此时数组的首元素 arr[0] 就是最大值）。

2. 将堆顶元素（最大值）与数组末尾元素交换，将最大值“沉”到数组尾部。

3. 将剩余的元素重新调整为最大堆（范围减 1），重复上述步骤，直到整个数组有序。

具体实现：

Java

import 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$ 的最小堆。

1. 先将前 $K$ 个元素放入最小堆中。此时堆顶是这 $K$ 个数中最小的。

2. 遍历剩余的元素：如果元素大于堆顶元素，说明堆顶那个“菜鸡”不配留在 Top K 里。我们把堆顶踢出 (poll)，将新元素加进去 (offer)。

3. 遍历结束后，堆里剩下的就是最大的 $K$ 个数！

整体时间复杂度为 $O(N \log K)$，非常适合处理海量数据流。

具体实现：

Java

import java.util.PriorityQueue;
import java.util.Arrays;

public class TopK {
    public static int[] findTopK(int[] nums, int k) {
        // 创建一个容量为 K 的最小堆
        PriorityQueue<Integer> 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]
    }
}

五、 源码探秘：Java PriorityQueue 的扩容原理

既然 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);
}

扩容规则总结：

1. 当原容量比较小（小于 64）时：

   扩容步长为 oldCapacity + 2。相当于扩大了一倍多一点（近似于 2 * oldCapacity + 2）。因为容量小的时候，频繁扩容的概率高，直接翻倍可以减少扩容次数。

2. 当原容量比较大（大于等于 64）时：

   扩容步长为 oldCapacity >> 1（即原容量的一半）。相当于扩大为原来的 1.5 倍。因为当容量已经很大时，如果继续翻倍，可能会导致大量的内存空间浪费甚至内存溢出 (OOM)，所以扩容策略变得更加平缓。