49 · 堆与对顶堆、启发式合并

堆只有三条命令：push、pop、top，每次 O(log n)。第 17 节的贪心题里就用它挑最大 / 最小，这一节把它当积木：两块拼成对顶堆求中位数，多块拼起来时讨论怎么合并最省，最后看一眼支持 O(log n) 合并的左偏树。

例题里真正要维护的是“第 k 小”。先看两个这一节才会用到的成员函数，后面的合并与对顶堆都靠它们。

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<pair<int, int>> pq;    // 先比 first，first 相同再比 second

    pq.emplace(3, 7);                     // 原地构造 pair(3, 7)
    pq.push(make_pair(4, 1));             // 老写法：先造对象再搬进去
    pq.push({5, 0});                      // 花括号也行

    cout << pq.top().first << " " << pq.top().second << "\n";   // 5 0
    cout << pq.size() << "\n";                                  // 3
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> a, b;
    a.push(1); a.push(2);          // a = {1, 2}，堆顶 2
    b.push(9);                     // b = {9}

    a.swap(b);                     // O(1)：现在 a = {9}，b = {1, 2}
    cout << a.top() << "\n";       // 9

    priority_queue<int> empty;
    a.swap(empty);                 // 也是 O(1) 清空

    // 大根堆和小根堆是两个类型，下面这行编译不过：
    // priority_queue<int> big;
    // priority_queue<int, vector<int>, greater<int>> small;
    // big.swap(small);            // error: no matching function for call to swap
    return 0;
}

// ① 按大小关系归类
if (big.empty() || x <= big.top()) big.push(x); else small.push(x);

// ② 按数量关系拉平：big 的大小只能是 small 或 small + 1
if ((int)big.size() > (int)small.size() + 1) { small.push(big.top()); big.pop(); }
else if (big.size() < small.size())          { big.push(small.top()); small.pop(); }

// ③ 第奇数个数读完后，堆顶就是中位数
if (i & 1) printf("%d\n", big.top());

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    priority_queue<int> big;                                 // 大根堆：存较小的一半
    priority_queue<int, vector<int>, greater<int>> small;     // 小根堆：存较大的一半

    for (int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);

        // ① 先按大小关系决定去左边还是右边
        if (big.empty() || x <= big.top()) big.push(x);
        else small.push(x);

        // ② 再按数量关系拉平：big 的大小只能是 small 或 small + 1
        if ((int)big.size() > (int)small.size() + 1) {
            small.push(big.top()); big.pop();
        } else if (big.size() < small.size()) {
            big.push(small.top()); small.pop();
        }

        // ③ 第奇数个数读完后总数为奇数，big 比 small 多一个，堆顶即中位数
        if (i & 1) printf("%d\n", big.top());
    }
    return 0;
}

priority_queue 没有 merge，也没有迭代器，两个堆的内部数组不能直接拼（拼完不是堆）。想合并只有一条路：把一个堆的元素 pop 出来、push 进另一个。

单次合并的代价是 O(m log(n+m))，m 是较小堆的大小。只合一次的话这样足够。真正的麻烦是“N 个集合反复两两合并”——这时合并顺序决定复杂度。

// 把 b 的全部元素搬进 a，并保证搬的是较小的那一堆
void mergeInto(priority_queue<int>& a, priority_queue<int>& b) {
    if (a.size() < b.size()) a.swap(b);      // ★ O(1)：只交换两个底层容器
    while (!b.empty()) {                     // 现在 b 一定是小的
        a.push(b.top());
        b.pop();
    }
}

同一个“小并大”的思想搬到树上，就是 DSU on tree（树上启发式合并）。它解决的问题很固定：对每个点 u，回答一个只与 u 的子树有关的问题，而这个问题支持“加点、删点、随时取答案”这三种操作。

做法四步：① 求子树大小与重儿子；② 先递归所有轻儿子，算完把它们的贡献清空；③ 再递归重儿子，算完保留它的贡献；④ 把轻儿子的子树暴力加回来，加上自己，此时的答案就是 u 的答案；若 u 是轻儿子，用完再清空。

复杂度 O(n log n)：一个点被“暴力加入”的次数，等于它到根路径上轻边的条数；走一条轻边意味着父的子树大小至少是子的两倍，所以轻边不超过 log₂ n 条。每次加入是 O(1)（桶计数），合计 n log₂ n。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;

int n, c[MAXN];                     // c[u] = 点 u 的颜色
vector<int> g[MAXN];
int sz[MAXN], son[MAXN];            // 子树大小、重儿子
int cnt[MAXN], mx;                  // cnt[颜色] 出现次数；mx = 当前最大出现次数
long long sum, ans[MAXN];           // sum = 出现次数等于 mx 的颜色编号之和

void dfs1(int u, int p) {           // 第一遍：子树大小与重儿子
    sz[u] = 1;
    for (int v : g[u]) if (v != p) {
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;   // sz[0] = 0，所以 son 初值 0 也能比
    }
}

void add(int u, int p, int d) {     // 把 u 子树的颜色整体加进 / 移出桶
    cnt[c[u]] += d;
    if (d > 0) {                    // 只加的时候维护答案，清空时不用管
        if (cnt[c[u]] > mx) { mx = cnt[c[u]]; sum = c[u]; }
        else if (cnt[c[u]] == mx) sum += c[u];
    }
    for (int v : g[u]) if (v != p) add(v, u, d);
}

void dfs2(int u, int p, bool keep) {
    for (int v : g[u]) if (v != p && v != son[u]) dfs2(v, u, false);   // 轻儿子：算完清空
    if (son[u]) dfs2(son[u], u, true);                                 // 重儿子：算完保留
    for (int v : g[u]) if (v != p && v != son[u]) add(v, u, 1);        // 轻儿子暴力补回来

    cnt[c[u]]++;                                                       // 加上自己
    if (cnt[c[u]] > mx) { mx = cnt[c[u]]; sum = c[u]; }
    else if (cnt[c[u]] == mx) sum += c[u];
    ans[u] = sum;

    if (!keep) { add(u, p, -1); mx = 0; sum = 0; }                     // 用完清空并复位
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0, false);
    for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

启发式合并的 O(n log² n) 里，多出来的那个 log 是“每个元素都要 push 一次”。如果能直接合并两个堆、每次只走 O(log n) 步，总代价就降到 O(n log n)。这就是可并堆：左偏树是最常用的实现。

左偏树用 ls[]、rs[] 两个数组表示二叉树，另外记一个 dist。它只保证一件事：每个点的左子树 dist ≥ 右子树 dist。于是从根一路往右走的“右路径”很短，merge 只沿右路径递归，自然 O(log n)——而右路径长度不超过 log₂(n+1)，这一点在数学补给里证。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int ls[MAXN], rs[MAXN], dist[MAXN], val[MAXN];

// 合并两棵左偏树（大根堆），返回新根
int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (val[x] < val[y]) swap(x, y);                     // x 当根
    rs[x] = merge(rs[x], y);                             // 只递归右子树
    if (dist[ls[x]] < dist[rs[x]]) swap(ls[x], rs[x]);   // 维持左偏
    dist[x] = dist[rs[x]] + 1;
    return x;
}

// 删除堆顶：合并根的左右子树即可，O(log n)
int pop(int x) { return merge(ls[x], rs[x]); }

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> val[i]; dist[i] = 1; }  // ★ 每个点单独成堆：dist = 1
    int root = 0;
    for (int i = 1; i <= n; ++i) root = merge(root, i);           // 全部并成一个大根堆
    while (root) { cout << val[root] << " "; root = pop(root); }  // 降序输出
    return 0;
}

三者的取舍：只合一次——直接 pop/push 搬，代码最短；反复合并但不要求最优——启发式合并，用 STL 就够；合并次数多、常数敏感——左偏树。选哪个看合并次数和常数，不看理论复杂度好不好看。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n;
    scanf("%d%d", &m, &n);

    vector<int> a(m + 1), u(n + 1);
    for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
    for (int j = 1; j <= n; ++j) scanf("%d", &u[j]);

    priority_queue<int> big;                                  // 存最小的 i 个数
    priority_queue<int, vector<int>, greater<int>> small;      // 存剩下的
    int q = 1;                                                 // 下一次要处理的 GET 编号

    for (int i = 1; i <= m; ++i) {
        // ADD a[i]
        if (big.empty() || a[i] <= big.top()) big.push(a[i]);
        else small.push(a[i]);

        // 第 i 次 ADD 之后可能有若干次 GET（u 可能重复）
        while (q <= n && u[q] <= i) {
            while ((int)big.size() < q) { big.push(small.top()); small.pop(); }  // 补到 q 个
            while ((int)big.size() > q) { small.push(big.top()); big.pop(); }    // 多的送回右边
            printf("%d\n", big.top());     // 第 q 小
            ++q;
        }
    }
    return 0;
}