配对堆

介绍

松散多叉树，满足堆序性，可实现 $O(1)$ 合并

存储

一般用孩子兄弟表示法，因为需要大量和兄弟节点合并

struct Node{
    int val = 0;
    int ch = 0, fa;
    int bro = 0, prev = 0;
    Node(int v): val(v) {}
};
vector<Node> hp(1);

操作

合并

直接把一个堆挂到另一个堆的第一个儿子

小顶堆为例

int merge(int x, int y){
    // 空堆直接返回另一个堆
    if(!x || !y) return x | y;
    // 交换两个堆，保证小顶堆在左边
    if(hp[x].val > hp[y].val) swap(x, y);
    // 将 y 挂到 x 的第一个儿子
    hp[y].bro = hp[x].ch;
    hp[hp[x].ch].prev = y;
    hp[y].fa = x;
    hp[x].ch = y;
    return x;
}

插入

把新节点当做一个堆，合并

int insert(int x, int k){
    hp.emplace_back(k);
    return merge(x, hp.size() - 1);
}

弹出

• 从左向右，两两合并儿子
• 从右向左合并所有刚才合并的堆

int merge_pair(int x){
    // 空堆或只有一个儿子直接返回
    if(!x || !hp[x].bro) return x;
    // 找到一轮合并的兄弟，和二轮合并的兄弟
    int a = x, b = hp[a].bro, c = hp[b].bro;
    // 清除旧指针
    hp[a].bro = hp[b].bro = 0;
    hp[a].fa = hp[b].fa = 0;
    // 递归完成两轮合并
    return merge(merge(a, b), merge_pair(c));
}
int pop(int x){
    if(!x) return 0;
    return merge_pair(hp[x].ch);
}

减小值

• 把要减小的节点和挂载的小堆从堆里摘掉
• 再和堆根合并

还要用并查集维护堆顶映射，这里不演示了

// k < hp[x].val
int decrease(int x, int k){
    if(!x) return 0;
    // 获取堆顶
    int root;
    // 摘掉小堆
    int &fa = hp[x].fa, &bro = hp[x].bro, &prev = hp[x].prev;
    if(prev) hp[prev].bro = bro;
    else hp[fa].ch = bro;
    if(bro) hp[bro].prev = hp[x].prev;
    fa = bro = prev = 0;
    // 重新合并
    hp[x].val = k;
    return merge(x, root);
}

删除

• 把值减小到负无穷
• 弹出

int del(int x){
    if(!x) return 0;
    return pop(decrease(x, INT_MIN));
}

复杂度

• 合并：$O(1)$
• 弹出：均摊 $O(\log n)$
• 插入：$O(1)$
• 减小值：$O(1)$
• 删除：均摊 $O(\log n)$