數(shù)據(jù)結(jié)構(gòu): 可合并堆-左偏樹
來自維基百科
左偏樹(英語: leftist tree或leftist heap), 也可稱為左偏堆, 左傾堆, 是計(jì)算機(jī)科學(xué)中的一種樹, 是一種優(yōu)先隊(duì)列實(shí)現(xiàn)方式, 屬于可并堆.
左偏堆的合并操作的最壞情況復(fù)雜度為O(log n), 而完全二叉堆為O(n), 所以左偏堆適合基于合并操作的情形.
左偏樹的結(jié)構(gòu)和性質(zhì)
左偏樹是可以合并的二叉堆, 首先滿足作為堆的基本性質(zhì):
- 樹形結(jié)構(gòu)
- 節(jié)點(diǎn)儲(chǔ)存信息, 有優(yōu)先級
- 每個(gè)節(jié)點(diǎn)的優(yōu)先級大于其子節(jié)點(diǎn)的優(yōu)先級
此外, 左偏樹有一些額外的性質(zhì), 來保證它合并的效率.
左偏樹的節(jié)點(diǎn)至少需要保存:
- 左右子樹節(jié)點(diǎn) lc, rc
- 該節(jié)點(diǎn)到 有空子節(jié)點(diǎn)的節(jié)點(diǎn) 的最短距離 h
- 優(yōu)先級權(quán)值 w
有空子節(jié)點(diǎn)的節(jié)點(diǎn), 就是指子節(jié)點(diǎn)數(shù)不為2的節(jié)點(diǎn)
除了堆的性質(zhì), 左偏樹還滿足 "左偏" 的性質(zhì), 這一點(diǎn)保證它的合并效率是O(log n)
即每個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)的h不小于右子節(jié)點(diǎn)的h, 因而有 h[rt] = h[rc[rt]] + 1
下圖即是一棵左偏樹, 節(jié)點(diǎn)上即權(quán)值(優(yōu)先級), 小根堆, 藍(lán)色數(shù)字為h
(注意, 左偏樹的左子樹一定不小于右子樹)
左偏樹的操作
同樣, 左偏樹可以做到普通的堆可以做到的:
- 插入元素 O(log n)
- 查詢最值 O(1)
- 刪除堆頂 O(log n)
而且還可以做到額外的:
- 合并 O(log n)
并且, 插入和刪除都是基于合并的:
- 插入即合并原樹和一個(gè)新節(jié)點(diǎn)
- 刪除即合并根的兩個(gè)子樹
左偏樹的合并操作
以小根堆為例:
假如要合并兩個(gè)堆 A, B
首先令 w[A] < w[B], 然后進(jìn)行合并merge(A, B)
在該函數(shù)中:
- 如果 w[rc[A]] < w[B], merage(rc[A], B)
- 如果 w[rc[A]] > w[B], 交換 A的右子樹 和 B, 然后繼續(xù)merage(rc[A], B)
- 如果 A的右子樹 或 B 為空, 則直接連接, 結(jié)束
如下圖演示:
可以看得出來, 這一番操作后失去了左偏的性質(zhì), 所以還要在遞歸回溯的過程中維護(hù)左偏性質(zhì):
如果節(jié)點(diǎn)左子節(jié)點(diǎn)的h小于右子節(jié)點(diǎn)的h, 則交換左右子樹, 維護(hù)該節(jié)點(diǎn)的h
合并操作的偽代碼
merge返回合并之后的樹根
仍然以小根堆為例
merge(A, B)
{
if(A == NULL) return B;
if(B == NULL) return A;
if(w[A] > w[B]) swap(A, B);
rc[A] = merge(rc[A], B);
/* 維護(hù)左偏性質(zhì) */
if(h[lc[A]] < h[rc[A]]) swap(lc[A], rc[A]);
/* 維護(hù)節(jié)點(diǎn) A 的 h值 */
if(rc[A] == NULL) h[A] = 0;
else h[A] = h[rc[A]] + 1;
return A;
}
完整代碼
NODE_NUM 為最大節(jié)點(diǎn)數(shù), 所有的樹的節(jié)點(diǎn)都在lt數(shù)組里
若改成大根堆只需要修改結(jié)構(gòu)體里為 w > k.w
- 新建一棵樹: rt = new_node(w);
- 合并兩棵樹: rt = merge(rt, rt2);
- 插入新節(jié)點(diǎn): rt = insert(rt, w);
- 刪除根節(jié)點(diǎn): rt = del(rt);
- 返回堆頂值: lt[rt].w
#define NODE_NUM 1000005
struct node {
int lc, rc;
int w, h;
bool operator < (const node &k) {
return w < k.w;
}
}lt[NODE_NUM];
int cnt, root;
//合并以A為根和以B為根的樹
int merge(int A, int B)
{
if(!A) return B;
if(!B) return A;
if(lt[B] < lt[A]) swap(A, B);
if(lt[B] < lt[lt[A].rc]) swap(lt[A].rc, B);
lt[A].rc = merge(lt[A].rc, B);
if(lt[lt[A].lc].h < lt[lt[A].rc].h) {
swap(lt[A].lc, lt[A].rc);
}
if(lt[A].rc) lt[A].h = lt[lt[A].rc].h + 1;
else lt[A].h = 0;
return A;
}
//新建一個(gè)節(jié)點(diǎn)
int new_node(int w)
{
lt[++cnt].w = w;
lt[cnt].h = lt[cnt].rc = 0;
return cnt;
}
//插入一個(gè)權(quán)值為w的節(jié)點(diǎn)
int insert(int A, int w)
{
return merge(A, new_node(w));
}
//刪除堆頂
int del(int A)
{
return merge(lt[A].lc, lt[A].rc);
}
