左偏树模板

  • 2018-03-03
  • 0
  • 0

左偏树 (Leftist Tree) 是一种特殊的堆有序 (heap-ordered) 二叉树。

普通的二叉堆合并的复杂度为 O(n),即使采用启发式合并也需要 O(log2n) 的时间。

假定我们的合并方法是将“副堆”往“主堆”右子树中合适的位置插入。

我们发现,合并的最坏情况出现在二叉堆成为一条右链时。

考虑到交换左右子树不会破坏堆的性质,我们可以通过该操作减小堆的深度

玄学的方法是每次插入时都交换经过节点的左右子树,这样可以在一定程度上使左右子树大小相近,做到单次均摊 logn 的复杂度。这类数据结构叫作斜堆

而左偏树是斜堆的一种较为珂学科学的实现方法。

我们发现,堆合并的效率取决于主堆右链的长度。因为只要递归到有一个子树为空则合并完成。

对于每个节点,增加一个成员变量 dist,表示该节点起右链的长度

每次合并时,仅当左儿子的 dist 小于右儿子的 dist 时交换左右子树,保证右链不会过长。

这样就可以做到单次严格 logn 的复杂度。

模板题:洛谷 3377 【模板】左偏树(可并堆)

注意删除节点时要将其子树的父指针置为子树本身

Problem:

题目描述

如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:

操作1: 1 x y 将第x个数和第y个数所在的小根堆合并(若第x或第y个数已经被删除或第x和第y个数在同一个堆内,则无视此操作)

操作2: 2 x 输出第x个数所在的堆最小数,并将其删除(若第x个数已经被删除,则输出-1并无视删除操作)

输入输出格式

输入格式:

第一行包含两个正整数N、M,分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数,其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数,表示一条操作,格式如下:

操作1 : 1 x y

操作2 : 2 x

输出格式:

输出包含若干行整数,分别依次对应每一个操作2所得的结果。

输入输出样例

输入样例#1:

5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2
输出样例#1:

1
2

说明

当堆里有多个最小值时,优先删除原序列的靠前的,否则会影响后续操作1导致WA。

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=1000,M<=1000

对于100%的数据:N<=100000,M<=100000

样例说明:

初始状态下,五个小根堆分别为:{1}、{5}、{4}、{2}、{3}。

第一次操作,将第1个数所在的小根堆与第5个数所在的小根堆合并,故变为四个小根堆:{1,3}、{5}、{4}、{2}。

第二次操作,将第2个数所在的小根堆与第5个数所在的小根堆合并,故变为三个小根堆:{1,3,5}、{4}、{2}。

第三次操作,将第2个数所在的小根堆的最小值输出并删除,故输出1,第一个数被删除,三个小根堆为:{3,5}、{4}、{2}。

第四次操作,将第4个数所在的小根堆与第2个数所在的小根堆合并,故变为两个小根堆:{2,3,5}、{4}。

第五次操作,将第2个数所在的小根堆的最小值输出并删除,故输出2,第四个数被删除,两个小根堆为:{3,5}、{4}。

故输出依次为1、2。

Code: O(N+MlogN) [6324K, 60MS]

// 左偏树 (2018.3.3)
// 洛谷 3377 【模板】左偏树(可并堆)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100005;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int N, M, a[MAXN], topp = 0;

struct Node{
	int val, dist;
	Node *lc, *rc, *fa;
	bool del;
} pool[MAXN], *nul = pool;  // Avoid using NULL

inline void build(int *a, int n){
	nul->val = nul->dist = -1, nul->del = 1;
	for(register int i = 1; i <= n; i++){
		pool[i].val = a[i], pool[i].dist = 0;
		pool[i].lc = pool[i].rc = nul, pool[i].fa = &pool[i];
		pool[i].del = 0;
	}
}

inline Node* find(Node *u) {while(u->fa != u) u = u->fa; return u;}

inline Node* merge(Node *u, Node *v){
	if(u == nul) return v;
	if(v == nul) return u;
	if(u->val == v->val ? u > v : u->val > v->val) swap(u, v);
	u->rc = merge(u->rc, v), u->rc->fa = u;
	if(u->lc->dist < u->rc->dist) swap(u->lc, u->rc);
	u->dist = u->rc->dist + 1;
	return u;
}

inline void pop(Node *u){
	Node *r = merge(u->lc, u->rc);
	r->fa = r, u->del = 1;
}

int main(){
	getint(N), getint(M);
	for(register int i = 1; i <= N; i++) getint(a[i]);
	build(a, N);
	for(register int i = 1; i <= M; i++){
		int opt, x, y; getint(opt);
		if(opt == 1){
			getint(x), getint(y);
			if(pool[x].del || pool[y].del) continue;
			Node *rx = find(&pool[x]), *ry = find(&pool[y]);
			if(rx == ry) continue;
			merge(rx, ry);
		}
		else if(opt == 2){
			getint(x);
			if(pool[x].del) {puts("-1"); continue;}
			Node *rx = find(&pool[x]);
			printf("%d\n", rx->val);
			pop(rx);
		}
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai