Heap

Leftist Tree (Persistent)

持久化可并堆，自带垃圾回收。

namespace LTree {
    extern struct P* null, *pit;
    queue<P*> trash;
    const int M = 1E6 + 100;
    struct P {
        P *ls, *rs;
        LL v;
        int d;
        void operator delete (void* ptr) { trash.push((P*)ptr); }
        void* operator new(size_t size) {
            if (trash.empty()) return pit++;
            void* ret = trash.front(); trash.pop(); return ret;
        }
    } pool[M], *pit = pool, *null = new P{0, 0, -1, -1};
    P* N(LL v, P* ls = null, P* rs = null) {
        if (ls->d < rs->d) swap(ls, rs);
        return new P{ls, rs, v, rs->d + 1};
    }
    P* merge(P* a, P* b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a->v < b->v) return N(a->v, a->ls, merge(a->rs, b));
        else return N(b->v, b->ls, merge(b->rs, a));
    }

    LL pop(P*& o) {
        LL ret = o->v;
        o = merge(o->ls, o->rs);
        return ret;
    }
}

pb_ds

如果不需要持久化，只需要值的修改或者堆的合并，那么使用 pb_ds 版本，其中的配对堆足够优秀了。

#include<ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;

typedef __gnu_pbds::priority_queue<LL, less<LL>, pairing_heap_tag> PQ;
__gnu_pbds::priority_queue<int, cmp, pairing_heap_tag>::point_iterator it;
PQ pq, pq2;

int main() {
    auto it = pq.push(2);
    pq.push(3);
    assert(pq.top() == 3);
    pq.modify(it, 4);
    assert(pq.top() == 4);
    pq2.push(5);
    pq.join(pq2);
    assert(pq.top() == 5);
}