堆与优先队列 (Heap & Priority Queue)

堆（Heap）是一种满足特定偏序关系的完全二叉树结构。最大（大顶）堆中任意父节点均不小于其子节点，最小（小顶）堆中任意父节点均不大于其子节点。在算法竞赛中，常用于在 \(\mathcal{O}(1)\) 时间内获取极值，并在 \(\mathcal{O}(\log n)\) 内维护动态集合。

---

1. 手写二叉堆与线性建堆

虽然 C++ STL 提供了 std::priority_queue，但手写二叉堆允许我们实现线性 \(\mathcal{O}(n)\) 建堆、任意指定位置元素的修改或删除等高级操作。

使用 1-indexed 连续数组存储完全二叉树：节点 \(i\) 的左孩子为 \(2i\)，右孩子为 \(2i + 1\)，父节点为 \(\lfloor i / 2 \rfloor\)。

#include <vector>
#include <algorithm>

template <typename T = int, typename Compare = std::less<T>>
struct BinaryHeap {
    std::vector<T> heap;
    Compare cmp; // 默认 std::less 为大顶堆

    BinaryHeap() { heap.push_back(T()); } // 0 号位置占位

    // O(n) 线性建堆
    BinaryHeap(const std::vector<T> &data) {
        heap.push_back(T());
        for (const auto &val : data) heap.push_back(val);
        for (int i = size() / 2; i >= 1; --i) {
            sift_down(i);
        }
    }

    int size() const { return heap.size() - 1; }
    bool empty() const { return size() == 0; }
    const T& top() const { return heap[1]; }

    void sift_up(int i) {
        while (i > 1 && cmp(heap[i / 2], heap[i])) {
            std::swap(heap[i], heap[i / 2]);
            i /= 2;
        }
    }

    void sift_down(int i) {
        int n = size();
        while (2 * i <= n) {
            int child = 2 * i;
            if (child + 1 <= n && cmp(heap[child], heap[child + 1])) {
                child++; // 选取满足条件的更优孩子
            }
            if (cmp(heap[i], heap[child])) {
                std::swap(heap[i], heap[child]);
                i = child;
            } else {
                break;
            }
        }
    }

    void push(const T &val) {
        heap.push_back(val);
        sift_up(size());
    }

    void pop() {
        if (empty()) return;
        heap[1] = heap.back();
        heap.pop_back();
        if (!empty()) sift_down(1);
    }
};

---

2. 对顶堆维护动态中位数 (Dual Heap)

对顶堆是算法竞赛中极其经典的模型：利用一个大顶堆（维护较小的一半元素）和一个小顶堆（维护较大的一半元素），动态维护中位数或第 \(k\) 极值。

• 插入元素：\(\mathcal{O}(\log n)\)
• 查询中位数：\(\mathcal{O}(1)\)

#include <queue>
#include <vector>

template <typename T>
struct MedianFinder {
    std::priority_queue<T> max_heap; // 存放较小的一半
    std::priority_queue<T, std::vector<T>, std::greater<T>> min_heap; // 存放较大的一半

    void add(T val) {
        if (max_heap.empty() || val <= max_heap.top()) {
            max_heap.push(val);
        } else {
            min_heap.push(val);
        }
        // 动态平衡两个堆的大小: 保证 max_heap.size() == min_heap.size() 或 + 1
        if (max_heap.size() > min_heap.size() + 1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        } else if (min_heap.size() > max_heap.size()) {
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
    }

    // 获取当前中位数 (奇数个为正中元素，偶数个通常取较小或较大中位数)
    T get_median() const {
        return max_heap.top();
    }
};

---

3. 左偏树 (Leftist Tree / 可并堆)

普通二叉堆合并两堆的复杂度高达 \(\mathcal{O}(n)\)。左偏树通过维护每个节点的“距离（\(\text{dist}\)，即到达最近后代外节点的距离）”，确保其向左偏倾，从而在 \(\mathcal{O}(\log n)\) 时间内完成两堆高效合并。

#include <iostream>
#include <vector>
#include <algorithm>

struct LeftistTree {
    struct Node {
        int val;
        int l = 0, r = 0;
        int dist = 0;
    };

    std::vector<Node> tree;

    LeftistTree(int capacity = 100000) {
        tree.reserve(capacity + 5);
        tree.push_back({0, 0, 0, -1}); // 0 节点作为空节点, dist[0] = -1
    }

    int new_node(int val) {
        tree.push_back({val, 0, 0, 0});
        return tree.size() - 1;
    }

    // 核心操作: 合并两棵以 x 和 y 为根的左偏树 (小顶堆语义)
    int merge(int x, int y) {
        if (!x || !y) return x ? x : y;
        // 小顶堆: 确保 x 的权值较小
        if (tree[x].val > tree[y].val) std::swap(x, y);

        tree[x].r = merge(tree[x].r, y);

        // 维护左偏性质: 左孩子 dist >= 右孩子 dist
        if (tree[tree[x].l].dist < tree[tree[x].r].dist) {
            std::swap(tree[x].l, tree[x].r);
        }
        tree[x].dist = tree[tree[x].r].dist + 1;
        return x;
    }

    // 删除堆顶: 直接合并左右子树
    int pop(int root) {
        return merge(tree[root].l, tree[root].r);
    }
};

---

4. STL std::priority_queue 常用写法速查

#include <queue>
#include <vector>

// 1. 默认大顶堆
std::priority_queue<int> max_pq;

// 2. 小顶堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

// 3. 结构体与自定义比较 (按权值升序排列的小顶堆)
struct Item {
    int id;
    long long cost;
    // 优先队列中若重载 operator<，默认是大顶堆
    // 若要 cost 小的在堆顶，需要 cost > other.cost (即反向定义小于号)
    bool operator<(const Item &other) const {
        return cost > other.cost;
    }
};
std::priority_queue<Item> pq;

---

复杂度对比表

堆类型	插入 (push)	获取堆顶 (top)	弹出堆顶 (pop)	合并两堆 (merge)	核心适用场景
二叉堆 (Binary Heap)	\(\mathcal{O}(\log n)\)	\(\mathcal{O}(1)\)	\(\mathcal{O}(\log n)\)	\(\mathcal{O}(n)\)	最常用通用优先队列、Dijkstra
对顶堆 (Dual Heap)	\(\mathcal{O}(\log n)\)	\(\mathcal{O}(1)\)	\(\mathcal{O}(\log n)\)	-	动态流数据中位数、第 \(k\) 大维护
左偏树 (Leftist Tree)	\(\mathcal{O}(\log n)\)	\(\mathcal{O}(1)\)	\(\mathcal{O}(\log n)\)	\(\mathcal{O}(\log n)\)	并查集维护多个独立堆的合并、反悔贪心

---

LeetCode 经典真题精选与题解提示

• LeetCode 215 - 数组中的第K个最大元素 (Kth Largest Element in an Array) 中等

  提示

  小顶堆求前 K 大 / 快速选择 (Quickselect)。

  • 维护大小为 \(k\) 的小顶堆（priority_queue<int, vector<int>, greater<int>>），遍历数组元素：当堆大小超过 \(k\) 时弹出堆顶，遍历结束后堆顶即为第 \(k\) 个最大元素，时间复杂度 \(\mathcal{O}(n \log k)\)。
  • 亦可用快速选择算法实现期望 \(\mathcal{O}(n)\) 复杂度。

• LeetCode 295 - 数据流的中位数 (Find Median from Data Stream) 困难

  提示

  对顶堆 (Dual Heap) 经典模板题。

  • 维护大顶堆 \(L\)（存较小的一半）和小顶堆 \(R\)（存较大的一半）。
  • 保持平衡不变量：\(|L| = |R|\) 或 \(|L| = |R| + 1\)。
  • 插入时间 \(\mathcal{O}(\log n)\)，获取中位数仅需 \(\mathcal{O}(1)\) 访问堆顶。

• LeetCode 23 - 合并 K 个升序链表 (Merge k Sorted Lists) 困难

  提示

  多路归并优先队列。

  • 将 \(k\) 个链表的头节点压入小顶堆。
  • 每次弹出值最小的节点接到合并链表末尾，并将该节点的 next 节点压入堆中。总时间复杂度 \(\mathcal{O}(N \log k)\)，其中 \(N\) 为节点总数。

• LeetCode 1675 - 数组的最小偏移量 (Minimize Deviation in Array) 困难

  提示

  大顶堆贪心收缩极差。

  • 奇数只能乘 2（且至多乘一次即变偶数），偶数可以除以 2 多次。
  • 预处理将所有奇数乘以 2，这样所有数都达到能变成的最大可能值，后续操作仅剩“将最大偶数除以 2”。
  • 将所有数放入大顶堆，维护全局当前最小值 min_val。每次取出堆顶最大值更新当前极差 ans = min(ans, max_val - min_val)，然后将堆顶除以 2 并更新 min_val 重新入堆，直到堆顶变为奇数无法再除 2 为止。