左偏樹（Leftist Heap/Tree）簡介及代碼，leftistheap
左偏樹是一種常用的優先隊列（堆）結構。與二叉堆相比，左偏樹可以高效的實現兩個堆的合並操作。
左偏樹實現方便，編程復雜度低，而且有著不俗的效率表現。
它的一個常見應用就是與並查集結合使用。利用並查集確定兩個元素是否在同一集合，利用左偏樹確定某個集合中優先級最高的元素。
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4
5 template <class T>
6 struct HeapNode
7 {
8 typedef HeapNode<T> Node;
9 Node* lch;
10 Node* rch;
11 T val;
12 int dist;
13
14 HeapNode(const T& _val):lch(0),rch(0),val(_val),dist(0) {}
15
16 void clear()
17 {
18 if(lch) lch->clear();
19 if(rch) rch->clear();
20 delete this;
21 }
22 };
23
24 template <class T,class Comp>
25 struct LeftistHeap
26 {
27 typedef HeapNode<T> Node;
28 typedef LeftistHeap<T,Comp> Heap;
29
30 Node* root;
31 Comp cmp;
32
33 LeftistHeap():root(0) {}
34 ~LeftistHeap()
35 {
36 clear();
37 }
38
39 void clear()
40 {
41 if(root) root->clear();
42 root=0;
43 }
44
45 Node* merge(Node* A,Node* B)
46 {
47 if(!A) return B;
48 if(!B) return A;
49
50 if(cmp(B->val,A->val)) std::swap(A,B);
51 A->rch=merge(B,A->rch);
52
53 if(!A->lch || A->rch->dist > A->lch->dist)
54 std::swap(A->lch,A->rch);
55 A->dist = (A->rch) ? A->rch->dist + 1 : 0 ;
56
57 return A;
58 }
59
60 void push(const T& _val)
61 {
62 Node* nNode=new Node(_val);
63 root=merge(root,nNode);
64 }
65
66 Heap& operator << (const T& _val)
67 {
68 push(_val);
69 return *this;
70 }
71
72 T top()
73 {
74 return root->val;
75 }
76
77 void pop()
78 {
79 Node* temp=root;
80 root=merge(temp->lch,temp->rch);
81 delete temp;
82 }
83
84 Heap& operator >> (T& _dest)
85 {
86 _dest=top();
87 pop();
88 return *this;
89 }
90
91 void merge(Heap& _other)
92 {
93 this->root=merge(this->root,_other.root);
94 _other.root=0;
95 }
96
97 bool empty()
98 {
99 return root==0;
100 }
101 };
Leftist Heap
定義左偏樹節點的“距離”（dist）為從其右子樹開始，一直向右走的路徑總長。特別地，若某個節點沒有右孩子，其dist值為0。
樹中的每個節點都必須滿足左孩子的dist值不小於右孩子（如果有的話）的dist值。
和大多數可並堆一樣，左偏樹的核心操作就是合並（Merge）操作。
（以下偽代碼以小根堆為例，節點的數據域記為val）
function merge(Node* A,Node* B)
if(A和B中某一個為空) return 另一個 //特判，同時也是遞歸終止的條件
交換A和B（如果需要的話），使得A的val小於B的val
A->rch = merge(B,A->rch)
if(A的左孩子的dist小於右孩子的dist或A的左孩子不存在) 交換A的左、右孩子
根據A的右孩子更新A的dist
return A
實現細節詳見代碼。
有了合並操作，其他的也就水到渠成了：
插入（push）：建立一個新節點，然後把它視為一個左偏樹，將其與已有的合並。
刪除（pop）：刪除其根節點，合並原先根節點的左右孩子。
附一道左偏樹+並查集的練習題：
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4
5 template <class T>
6 struct HeapNode
7 {
8 typedef HeapNode<T> Node;
9 Node* lch;
10 Node* rch;
11 T val;
12 int dist;
13
14 HeapNode(const T& _val):lch(0),rch(0),val(_val),dist(0) {}
15
16 void clear()
17 {
18 if(lch) lch->clear();
19 if(rch) rch->clear();
20 delete this;
21 }
22 };
23
24 template <class T,class Comp>
25 struct LeftistHeap
26 {
27 typedef HeapNode<T> Node;
28 typedef LeftistHeap<T,Comp> Heap;
29
30 Node* root;
31 Comp cmp;
32
33 LeftistHeap():root(0) {}
34 ~LeftistHeap()
35 {
36 clear();
37 }
38
39 void clear()
40 {
41 if(root) root->clear();
42 root=0;
43 }
44
45 Node* merge(Node* A,Node* B)
46 {
47 if(!A) return B;
48 if(!B) return A;
49
50 if(cmp(B->val,A->val)) std::swap(A,B);
51 A->rch=merge(B,A->rch);
52
53 if(!A->lch || A->rch->dist > A->lch->dist)
54 std::swap(A->lch,A->rch);
55 A->dist = (A->rch) ? A->rch->dist + 1 : 0 ;
56
57 return A;
58 }
59
60 void push(const T& _val)
61 {
62 Node* nNode=new Node(_val);
63 root=merge(root,nNode);
64 }
65
66 Heap& operator << (const T& _val)
67 {
68 push(_val);
69 return *this;
70 }
71
72 T top()
73 {
74 return root->val;
75 }
76
77 void pop()
78 {
79 Node* temp=root;
80 root=merge(temp->lch,temp->rch);
81 delete temp;
82 }
83
84 Heap& operator >> (T& _dest)
85 {
86 _dest=top();
87 pop();
88 return *this;
89 }
90
91 void merge(Heap& _other)
92 {
93 this->root=merge(this->root,_other.root);
94 _other.root=0;
95 }
96
97 bool empty()
98 {
99 return root==0;
100 }
101 };
102
103 #include <functional>
104
105 const int maxN=100005;
106
107 int N,M;
108 int idx[maxN];
109
110 int father(int x)
111 {
112 return idx[x]==x ? x : idx[x]=father(idx[x]) ;
113 }
114
115 LeftistHeap<int,std::greater<int> > heap[maxN];
116
117 void init()
118 {
119 for(int i=0;i<maxN;i++) heap[i].clear();
120 for(int i=0;i<maxN;i++) idx[i]=i;
121 }
122
123 bool solve()
124 {
125 init();
126
127 if(scanf("%d",&N)==EOF) return false;
128 for(int i=1;i<=N;i++)
129 {
130 int s; scanf("%d",&s);
131 heap[i].push(s);
132 }
133
134 scanf("%d\n",&M);
135 while(M--)
136 {
137 int mk1,mk2;
138 scanf("%d%d",&mk1,&mk2);
139
140 int f1=father(mk1);
141 int f2=father(mk2);
142 if(f1==f2)
143 {
144 printf("-1\n");
145 continue;
146 }
147
148 int s1,s2;
149 heap[f1]>>s1;
150 heap[f2]>>s2;
151
152 if(f1<f2)
153 {
154 idx[f2]=f1;
155 heap[f1].merge(heap[f2]);
156 if(heap[f1].empty()) printf("%d\n",std::max(s1,s2)>>1);
157 else printf("%d\n",std::max(heap[f1].top(),std::max(s1,s2)>>1));
158 heap[f1] << (s1>>1) << (s2>>1);
159 }
160 else
161 {
162 idx[f1]=f2;
163 heap[f2].merge(heap[f1]);
164 if(heap[f2].empty()) printf("%d\n",std::max(s1,s2)>>1);
165 else printf("%d\n",std::max(heap[f2].top(),std::max(s1,s2)>>1));
166 heap[f2] << (s1>>1) << (s2>>1);
167 }
168 }
169
170 return true;
171 }
172
173 int main()
174 {
175 while(solve());
176 return 0;
177 }
Problem：ZOJ P2334
