Leftist Tree

刚刚学的左偏树，可能是可并堆里面最简单的了。
模板是用来A洛谷里面的同名模板题，有兴趣可以去看看。
还是比较重要的数据结构23333。

传送门

直接上代码吧，有注释。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>

#define INF 247483647
#define N 3000100
using namespace std;

int read() {
    int rtn = 0;
    char ch = getchar();
    while (!isdigit(ch))ch = getchar();
    while (isdigit(ch))rtn = rtn * 10 + ch - '0', ch = getchar();
    return rtn;
}

struct node {
    int l, r, w, d, fa;
} heap[N];

int n, m;

int mergef(int x, int y) {
    if (!x || !y)return x + y;
    if (heap[x].w > heap[y].w || heap[x].w == heap[y].w && x > y)//维护小根堆,后半句纯属题目需要
        swap(x, y);
    heap[x].r = mergef(y, heap[x].r);//把另外一个树挂到右子树上,此时的右子树深度较小
    heap[heap[x].r].fa = x;//维护父节点的值
    if (heap[heap[x].l].d < heap[heap[x].r].d)//保证左子树比右子树更深
        swap(heap[x].l, heap[x].r);
    if (heap[x].r)heap[x].d = heap[heap[x].r].d + 1;//由于左偏树的右子树离根节点更近,所以他的dis由右子树决定
    else heap[x].d = 0;//定义没有右子树的节点dis为零
    return x;//返回合并之后的新根结点
}

int pop(int x) {
    int l = heap[x].l, r = heap[x].r;
    heap[x].l = heap[x].r = heap[x].w = -INF;
    heap[l].fa = l, heap[r].fa = r;
    return heap[x].fa = mergef(l, r);//由于很多其他节点的fa值没有改变,更改父节点
}


int findf(int x) {
    if (heap[x].fa == x)return x;
    return heap[x].fa = findf(heap[x].fa);
}

void Insert(int x) {
    heap[x].w = read(), heap[x].d = 0, heap[x].fa = x;
}

int main() {
    n = read(), m = read();
    heap[0].d = -1;
    for (int i = 1; i <= n; i++)Insert(i);
    while (m--) {
        int opt = read();
        if (opt == 1) {
            int x = read(), y = read();
            if (heap[x].w == -INF || heap[y].w == -INF)continue;
            int fx = findf(x), fy = findf(y);
            if (fx != fy)mergef(fx, fy);
        }
        if (opt == 2) {
            int x = read();
            if (heap[x].w == -INF) {
                printf("-1\n");
                continue;
            }
            printf("%d\n", heap[findf(x)].w);
            pop(findf(x));
        }
    }
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦