堆与优先队列

优先队列（Priority Queue）是一种按照优先级出队的数据结构，通常使用堆（Heap）作为其底层实现。与普通队列的"先进先出"不同，优先队列总是先处理优先级最高（或最低）的元素。

堆 (Heap)

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

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

堆的数组表示

由于堆是完全二叉树，可以用数组高效存储。对于数组索引为 i 的节点（从 0 开始）：

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

堆的核心操作

1. 上浮 (Sift Up)

当在堆末尾插入新元素时，将其与父节点比较并交换，直至满足堆性质。

// 小顶堆的上浮操作
private void siftUp(int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[parent] <= heap[i]) break;  // 满足堆性质
        swap(parent, i);
        i = parent;
    }
}

时间复杂度：$O(\log n)$，因为堆的高度为 $\log n$。

2. 下沉 (Sift Down)

当移除堆顶并用堆尾填补后，将其与最小（或最大）子节点比较并交换，直至满足堆性质。

// 小顶堆的下沉操作
private void siftDown(int i) {
    int n = size;
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;
        
        if (left < n && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < n && heap[right] < heap[smallest]) {
            smallest = right;
        }
        
        if (smallest == i) break;  // 满足堆性质
        
        swap(i, smallest);
        i = smallest;
    }
}

时间复杂度：$O(\log n)$

堆的完整实现

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;
    
    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }
    
    // 入队：添加到末尾，然后上浮
    public void offer(int val) {
        if (size >= capacity) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = val;
        siftUp(size);
        size++;
    }
    
    // 出队：保存堆顶，用末尾元素替换堆顶，然后下沉
    public int poll() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int result = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return result;
    }
    
    // 查看堆顶 - O(1)
    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        return heap[0];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int size() {
        return size;
    }
    
    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] <= heap[i]) break;
            swap(parent, i);
            i = parent;
        }
    }
    
    private void siftDown(int i) {
        while (true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int smallest = i;
            
            if (left < size && heap[left] < heap[smallest]) {
                smallest = left;
            }
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }
            
            if (smallest == i) break;
            
            swap(i, smallest);
            i = smallest;
        }
    }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

建堆操作

给定一个无序数组，如何将其建成堆？

方法一：逐个插入 - $O(n \log n)$

for (int val : arr) {
    offer(val);  // 每次插入都是 O(log n)
}

方法二：从底向上下沉 - $O(n)$

// 从最后一个非叶子节点开始，依次下沉
public void heapify(int[] arr) {
    this.heap = arr;
    this.size = arr.length;
    
    // 最后一个非叶子节点的索引是 (n/2 - 1)
    for (int i = size / 2 - 1; i >= 0; i--) {
        siftDown(i);
    }
}

为什么是 $O(n)$？

虽然下沉操作是 $O(\log n)$，但只有根节点可能需要下沉 $\log n$ 层，大部分节点（叶子节点和靠近叶子的节点）下沉的层数很少。数学推导可得总时间复杂度为 $O(n)$。

优先队列 (Priority Queue)

优先队列是一种抽象数据类型，支持以下操作：

• 插入元素
• 取出优先级最高（或最低）的元素
• 查看优先级最高（或最低）的元素

堆是实现优先队列的最佳数据结构。

时间复杂度

操作	时间复杂度	说明
offer (入队)	$O(\log n)$	需要上浮调整
poll (出队)	$O(\log n)$	需要下沉调整
peek (查看堆顶)	$O(1)$	直接访问数组首元素
建堆	$O(n)$	从底向上下沉

Java 中的 PriorityQueue

import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // 小顶堆（默认）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        
        // 或使用 Comparator
        PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(
            Comparator.reverseOrder()
        );
        
        // 基本操作
        minHeap.offer(5);
        minHeap.offer(1);
        minHeap.offer(3);
        
        System.out.println(minHeap.peek());   // 1（最小值，不出队）
        System.out.println(minHeap.poll());   // 1（出队）
        System.out.println(minHeap.poll());   // 3
        System.out.println(minHeap.poll());   // 5
    }
}

自定义对象的优先级

import java.util.PriorityQueue;
import java.util.Comparator;

// 方法一：实现 Comparable 接口
class Task implements Comparable<Task> {
    String name;
    int priority;
    
    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
    
    @Override
    public int compareTo(Task other) {
        return this.priority - other.priority;  // 小顶堆
    }
}

// 方法二：使用 Comparator
PriorityQueue<Task> queue = new PriorityQueue<>(
    Comparator.comparingInt(t -> t.priority)
);

// 方法三：Lambda 表达式
PriorityQueue<Task> queue2 = new PriorityQueue<>(
    (a, b) -> a.priority - b.priority
);

注意事项

1. PriorityQueue 不允许 null 元素
2. 不是线程安全的，多线程环境使用 PriorityBlockingQueue
3. 迭代器不保证有序，要按优先级遍历需要用 poll()

// 错误：迭代器不保证顺序
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);

for (int x : pq) {
    System.out.println(x);  // 输出顺序不确定！
}

// 正确：使用 poll 按优先级遍历
while (!pq.isEmpty()) {
    System.out.println(pq.poll());  // 1, 2, 3
}

经典应用

1. 前 K 个高频元素 (LeetCode 347)

使用小顶堆维护当前频率最高的 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;
}

为什么用小顶堆？

我们需要保留频率最高的 K 个元素。小顶堆的堆顶是当前最小的元素，当堆大小超过 K 时，移除堆顶（最小的），保留下来的就是最大的 K 个。

2. 数组中的第 K 个最大元素 (LeetCode 215)

public int findKthLargest(int[] nums, int k) {
    // 方法一：小顶堆，维护 K 个最大的元素
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    return minHeap.peek();
    
    // 方法二：大顶堆，弹出前 k-1 个元素
    // PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    // for (int num : nums) maxHeap.offer(num);
    // for (int i = 0; i < k - 1; i++) maxHeap.poll();
    // return maxHeap.peek();
}

3. 数据流的中位数 (LeetCode 295)

使用两个堆：大顶堆存储较小的一半，小顶堆存储较大的一半。

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;  // 存储较小的一半
    private PriorityQueue<Integer> minHeap;  // 存储较大的一半
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // 先加入 maxHeap
        maxHeap.offer(num);
        // 平衡：将 maxHeap 最大值移到 minHeap
        minHeap.offer(maxHeap.poll());
        
        // 保持 maxHeap 元素数 >= minHeap 元素数
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

4. 合并 K 个升序链表 (LeetCode 23)

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    
    // 小顶堆，按节点值排序
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        Comparator.comparingInt(node -> node.val)
    );
    
    // 将所有链表的头节点加入堆
    for (ListNode node : lists) {
        if (node != null) {
            minHeap.offer(node);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (!minHeap.isEmpty()) {
        ListNode minNode = minHeap.poll();
        current.next = minNode;
        current = current.next;
        
        if (minNode.next != null) {
            minHeap.offer(minNode.next);
        }
    }
    
    return dummy.next;
}

堆排序

堆排序是一种原地排序算法，时间复杂度 $O(n \log n)$。

public void heapSort(int[] arr) {
    int n = arr.length;
    
    // 建堆（大顶堆）
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
    
    // 排序：依次取出堆顶
    for (int i = n - 1; i > 0; i--) {
        // 交换堆顶和堆尾
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 对剩余元素重新堆化
        siftDown(arr, i, 0);
    }
}

private void siftDown(int[] arr, int n, int i) {
    while (true) {
        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) break;
        
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        
        i = largest;
    }
}

小结

本章我们学习了：

1. 堆的性质：大顶堆、小顶堆、数组表示
2. 堆的核心操作：上浮、下沉
3. 优先队列：按优先级出队的数据结构
4. 经典应用：Top K、中位数、合并有序链表
5. 堆排序：原地 $O(n \log n)$ 排序

堆是一种非常重要的数据结构，在需要快速获取最值的场景中应用广泛。

练习

1. LeetCode 215：数组中的第 K 个最大元素
2. LeetCode 347：前 K 个高频元素
3. LeetCode 295：数据流的中位数
4. LeetCode 23：合并 K 个升序链表
5. LeetCode 703：数据流中的第 K 大元素
6. 手动实现一个小顶堆（包含 offer、poll、peek）