P3378 题解

123456wjc · 2026-05-19 12:38:33 · 题解

本文介绍一种可并堆：配对堆。

题意简述

维护一个堆，支持插入元素、取最小值、删除最小值三种操作。

做法简析

配对堆是一种多叉树，满足堆的性质。其中每个节点的权值不大于它的后代。通常情况下，我们通过多叉树的孩子兄弟表示法用一颗二叉树存储、处理一个配对堆。

接下来是几种核心操作：

有了这些，我们就可以实现一个配对堆了。实际上，配对堆的时间复杂度分析非常困难，感兴趣可以查看 Iacono 在 2000 年提出的势能分析，其中 \operatorname{Meld} 的时间复杂度为 O(1)，\operatorname{Delete} 则是摊还 O(\log N)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
    int val;
    int child;//第一个孩子
    int sibling;//兄弟
}tr[N];
int meld(int x,int y){
    if(!x || !y) return x+y;
    if(tr[x].val>tr[y].val) swap(x,y);
    tr[y].sibling=tr[x].child;
    tr[x].child=y;
    return x;
}
int merge(int x){
    if(!x || !tr[x].sibling) return x;
    int p=tr[x].sibling;
    int q=tr[p].sibling;
    tr[x].sibling=tr[p].sibling=0;
    return meld(merge(q),meld(x,p));
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int root=0,top=0;
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            cin>>tr[++top].val;
            root=meld(root,top);
        }else if(op==2){
            cout<<tr[root].val<<'\n';
        }else{
            root=merge(tr[root].child);
        }
    }
}