配对堆

ajcxsu
ajcxsu 2018年06月03日
  • 38 次阅读

一种均摊复杂度很低的可并堆...


建议直接去看博客:
https://waautomaton.tk/2018/05/13/%E9%85%8D%E5%AF%B9%E5%A0%86/

据说常数/理解难易度吊打几种常见堆...虽然我太蒻还不知道斐波那契堆是个啥玩意qwq

核心操作是merge...但最复杂的操作是delete...

还可以改值...但我也不知道怎么改...(加上改值的操作的话就难上不少) (PS:根据维基,配对堆改值的复杂度$\log n$,但是有个Rank-paring Heaps可以做到$O(1)$改值,不过国内没有相关中文资料。)

这里想要说的话就是这玩意套到洛谷模板上去可能比较难打
原因就是洛谷模板上需要维护所属堆
而对于本堆来说,直接迭代查找父亲的话有点emmm

所以这里提供了一种路径压缩的方案...

不在内存中删去该点...将被删去的点的父亲指向新堆的根...
这样子的话就可以路径压缩了...
主要问题就是父指针要清干净...

关于效率问题,比我手写的指针左偏树快上一倍...
但是还是没有其他dalao写的好...大概是递归和指针还有大量函数调用的原因吧...

反正,也挺优秀了不是吗qwq

Code

// Code by ajcxsu
// Problem: paring heaps

#include<cstdio>
#include<iostream>
#include<cassert>
using namespace std;

inline void gn(int &x) {
    char ch=getchar();
    int pl=1;
    x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl;
}

const int N=1e5+10;
struct Node *nil;
struct Node {
    int v,id;
    bool deled;
    Node *ls, *rs, *f;
    Node(int val=0, int id=0):v(val), id(id) { ls=rs=f=nil; deled=0; }
    void cutf() { f=rs=nil; }
} *nd[N];
inline void ini() {
    nil=new Node;
    nil->ls=nil->rs=nil->f=nil;
}

inline Node* merge(Node *x, Node *y) {
    if(x==nil || x==y) return y;
    if(y==nil) return x;
    if(x->v>y->v || (x->v==y->v && x->id>y->id)) swap(x,y);
    y->rs=x->ls;
    x->ls=y, y->f=x, x->f=nil; // 注意把x的父指针置零
    return x;
}

inline Node* merges(Node *x) {
    Node *a=x->rs, *b=a->rs;
    x->cutf(), a->cutf();
    if(x==nil || a==nil) return x;
    return merge(merge(x,a), merges(b));
}

inline Node* del(Node *x) {
    x->deled=true;
    x->f=merges(x->ls);
    return x;
}

inline Node* Find(Node *x) {
    if(x->f==nil) return x;
    return x->f=Find(x->f);
}

int main() {
    ini();
    int n,m,v;
    gn(n), gn(m);
    for(int i=1;i<=n;i++) gn(v), nd[i]=new Node(v,i);
    int opt, a, b;
    while(m--) {
        gn(opt), gn(a);
        if(opt==1) {
            gn(b);
            if(nd[a]->deled || nd[b]->deled) continue;
            merge(Find(nd[a]), Find(nd[b]));
        }
        else {
            if(nd[a]->deled) printf("-1\n");
            else printf("%d\n",del(Find(nd[a]))->v);
        }
    }
    return 0;
}

本文链接:https://acxblog.site/archives/pairing_heaps.html
本文采用 CC BY-NC-SA 3.0 协议进行许可