堆与优先队列

优先队列（Priority Queue）按照优先级出队，通常使用堆（Heap）作为其底层实现。

堆 Heap

堆是一种特殊的完全二叉树，具有以下特性：

• 大顶堆：任意节点的值都大于等于其左右子节点的值。堆顶（根节点）是最大值。
• 小顶堆：任意节点的值都小于等于其左右子节点的值。堆顶（根节点）是最小值。

堆的数组表示

对于数组索引为 i 的节点（从 0 开始）：

• 左子节点索引：2 * i + 1
• 右子节点索引：2 * i + 2
• 父节点索引：(i - 1) / 2

堆的核心操作

1. 上浮 (Sift Up)：当在堆末尾插入新元素时，将其与父节点比较并交换，直至满足堆性质。
2. 下沉 (Sift Down)：当移除堆顶并用堆尾填补后，将其与最大/最小子节点比较并交换，直至满足堆性质。

优先队列 Priority Queue

优先队列按优先级处理元素，其操作时间复杂度通常为：

• offer (入队): O(log N)
• poll (出队): O(log N)
• peek (查看优先级最高): O(1)

Java 中的 PriorityQueue

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // 小顶堆（默认）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        
        minHeap.offer(5);
        minHeap.offer(1);
        minHeap.offer(3);
        
        System.out.println(minHeap.poll());  // 1（最小值）
        System.out.println(minHeap.poll());  // 3
        System.out.println(minHeap.poll());  // 5
    }
}

应用：前 K 个高频元素

使用小顶堆维护当前频率最高的 K 个元素。

public int[] topKFrequent(int[] nums, int k) {
    // 统计频率
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) freq.merge(num, 1, Integer::sum);
    
    // 小顶堆，按频率排序
    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> freq.get(a) - freq.get(b)
    );
    
    for (int num : freq.keySet()) {
        heap.offer(num);
        if (heap.size() > k) heap.poll();  // 移除频率最低的
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++) result[i] = heap.poll();
    return result;
}

练习

1. LeetCode 215：数组中的第 K 个最大元素 (考察堆或快速选择)
2. LeetCode 347：前 K 个高频元素
3. LeetCode 295：数据流的中位数 (使用两个堆)
4. LeetCode 23：合并 K 个升序链表 (使用优先队列)
5. 实现一个小顶堆 (练习 Sift Up 和 Sift Down)