可并堆(左偏树)

tech2023-01-15  109

如题意,即为可以合并的堆,在普通堆的基础上,我们在计入每个节点的父节点和该节点子树距离这个节点最近的叶子。我们在原堆的基础上追加一个性质:树的左孩子的距离不小于有孩子的距离(左偏),为什么要这么做呢,注意是建少合并时的数量。(启发式合并思想)。 于是合并时,我们,针对堆的性质,对于两个节点,我们尝试把权值大的点挂在到小的点上(小根堆),然后进行递归处理。处理完成后,然后如果左孩子的距离小于右孩子的距离,即交换两个节点。 另外有pop操作,我们取出首节点后,清除首节点,然后合并他的左右孩子即可。

#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); using namespace std; const int N = 1e5 + 5; struct Node { int dis, val; int l, r, f; } tr[N]; int fi(int x) { if (tr[x].f == x) return x; return tr[x].f = fi(tr[x].f); } int merge(int x, int y) { if (!x || !y) return x + y; if (tr[x].val > tr[y].val) swap(x, y); if (x > y && tr[x].val == tr[y].val) swap(x, y); int ls = tr[x].l, rs = tr[x].r; rs = merge(rs, y); if (tr[ls].dis < tr[rs].dis) swap(ls, rs); tr[ls].f = tr[rs].f = tr[x].f = x; tr[x].dis = tr[rs].dis+1; tr[x].l = ls; tr[x].r = rs; return x; } int top(int x) { if (tr[x].val == -1) return -1; int fa = fi(x); return tr[fa].val; } void pop(int x) { int fa = fi(x); int ls = tr[fa].l; int rs = tr[fa].r; tr[fa].val = -1; tr[ls].f = ls; tr[rs].f = rs; tr[fa].f = merge(ls, rs); } int main() { int n, m; scanf("%d%d", &n, &m); tr[0].dis =-1; for (int i = 1; i <= n; i++) tr[i].f = i, scanf("%d", &tr[i].val); while(m--) { int op; scanf("%d", &op); int a, b; if (op == 1) { scanf("%d%d", &a, &b); if (tr[a].val == -1) continue; if (tr[b].val == -1) continue; int fa = fi(a), fb = fi(b); if (fa != fb) tr[fa].f = tr[fb].f = merge(fa, fb); } else { scanf("%d", &a); printf("%d\n", top(a)); if (top(a) != -1) pop(a); } } return 0; }
最新回复(0)