左偏树
左偏树是⼀种不平衡的⼆叉树，特点是：堆+快速的合并
每个结点包含4个元素v,d,r,l。。。。
右边的D总是⽐左边的D⼩。。。向左偏。。。。
合并操作都是向右边的⼦树递归的，时间复杂度低O（log(n1)+log(n2)）。
因为合并⽐较快。。。所以。。基本操作⼤都是⽤合并完成的。。。。。写起来⾮常简单。。。。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5using namespace std;
6
7const int maxn=100010;
8int tot=0;
9
10struct leftistheapnode
11 {
12int v,d,r,l;
13 }heap[maxn];
14
15int merge(int x,int y)
16 {
17if(!x) return y; if(!y) return x;
18if(heap[x].v<heap[y].v) swap(x,y);///big root heap
19    heap[x].r=merge(heap[x].r,y);
20int l=heap[x].l,r=heap[x].r;
21if(heap[l].d<heap[r].d) swap(heap[x].l,heap[x].r);
22if(!heap[x].r) heap[x].d=0;
23else heap[x].d=heap[r].d+1;
24return x;
25 }
26
27int Init(int x)
28 {
29    tot++;
30    heap[tot].l=heap[tot].r=heap[tot].d=0;
31    heap[tot].v=x;
32return tot;
33 }
34
35int Insert(int x,int y)
36 {
37return merge(x,Init(y));
38 }
39
40int Pop(int x)
41 {
42return merge(heap[x].l,heap[x].r);
43 }
44
45int Top(int x) { return heap[x].v; }
46
47int main()
48 {
49return0;
leftist50 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。