可並堆——左偏樹實現
可並堆——左偏樹實現
可並堆
堆是優先隊列的一種實現方式，堆中父節點大於等於（或小於等於）兩子節點，每次的刪除，查詢，插入都是 \(O(log_2n)\) 的複雜度
- 我們考慮兩個堆的合併問題，如果讓小的堆合併到大的堆，一個一個插入，時間複雜度 \(O(nlog_2n)\) 效率往往不能滿足要求。我們需要一個合併複雜度大致為 \(O(log_2(m + n))\) 的可並堆
左偏樹
- 左偏樹可以用來實現這樣的可並堆，首先我們可以定義一個節點的dis值為這個節點的右節點的dis值+1，直觀地來說，一個節點的dis值就是從這個節點開始一直往右兒子走，最多能走多遠
- 然後對左偏樹可以這樣理解：
- 一棵左偏樹首先是個堆
- 對左偏樹上所有節點，都有
左兒子的dis值大於等於右兒子的dis值
– 定義結束，我們可能要問如何建一棵左偏樹？這裡我要說，左偏樹和傳統的堆不同，沒有pushup操作，左偏樹唯一的操作就是合併merge。
>也就是說，我們建立左偏樹，是將每個節點都看成一棵左偏樹，然後一步一步合併起來的，所以我們要先明確什麼是合併操作。
合併操作
對左偏樹最核心的合併操作，是這樣的(假設數越小優先順序越大)：
- 1.對以x，y為根節點的兩棵左偏樹合併，首先若x為空則合併結果為y，若y為空則合併結果為x（顯然）。
- 2.若都不為空，則檢查x，y節點的值，讓值大的節點與值小的節點的右兒子合併，這一步是為了維持堆的性質，保證父親小於子節點（以下假設x節點值更小）
- 3.合併之後，檢查x的左右兒子節點的dis值，如果左兒子的dis小於右兒子的dis，則交換左右兒子節點，這一步是為了維持左偏性質。
- 4.將x節點的dis設為右兒子節點的dis+1
如此遞歸操作即可在 \(O(log_2(m + n))\) 內完成兩個左偏樹的合併
其他操作
其他操作建立在合併之上，下面是常見的幾種。
-
插入節點
將待插入的節點作為一棵左偏樹與樹根合併即可
-
刪除
對於堆來說，刪除只能作用於根節點。所以把根節點與左右兒子斷開，然後合併左右子樹即可
-
建樹
對一個序列建左偏樹的較理想方式，是使用隊列，每次出隊兩棵樹（單節點也是左偏樹），將兩棵樹合併然後放在隊尾，直到隊內只剩下一棵左偏樹
其他事項
-
這裡可能有疑問，左偏樹深度怎麼保證？
-
事實上由定義，左偏樹是可以變成一條鏈的，這看上去對於堆的影響很小，但是這使得：
- 1.左偏樹不能用二進位運算的數組實現
- 2.尋找一個節點在左偏樹上的根，可能退化到 \(O(n)\) 複雜度(模板題中有涉及)
模板題 洛谷P3377
程式碼：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
struct ab
{
int v;
int dis;
int ls;
int rs;
int fa;
} aa[200005];
void sw(int& a, int& b)
{
int t = a;
a = b;
b = t;
}
bool bk[100005] = {0};
int merge(int x, int y)
{
if (!x)
{
return y;
}
if (!y)
{
return x;
}
if (aa[x].v > aa[y].v || (aa[x].v == aa[y].v && x > y))
{
sw(x, y);
}
aa[x].rs = merge(aa[x].rs, y);
aa[aa[x].rs].fa = x;
if (aa[x].ls)
{
aa[aa[x].ls].fa = x;
}
if (aa[aa[x].ls].dis < aa[aa[x].rs].dis)
{
sw(aa[x].ls, aa[x].rs);
}
if (!aa[x].rs)
{
aa[x].dis = 0;
}
else
{
aa[x].dis = aa[aa[x].rs].dis + 1;
}
return x;
}
int mn(int x)
{
if (aa[x].fa != x)
{
aa[x].fa = mn(aa[x].fa);
}
return aa[x].fa;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &aa[i].v);
aa[i].fa = i;
}
for (int i = 1; i <= m; ++i)
{
int sele;
scanf("%d", &sele);
if (sele == 1)
{
int xx, yy;
scanf("%d%d", &xx, &yy);
int mnx = mn(xx);
int mny = mn(yy);
if (bk[xx] || bk[yy] || mnx == mny)
{
continue;
}
merge(mn(xx), mn(yy));
}
else
{
int xx;
scanf("%d", &xx);
if (!bk[xx])
{
int id = mn(xx);
printf("%d\n", aa[id].v);
aa[aa[id].ls].fa = aa[id].ls;
aa[aa[id].rs].fa = aa[id].rs;
aa[id].v = 0;
aa[id].fa = merge(aa[id].ls, aa[id].rs);
bk[id] = true;
aa[id].ls = 0;
aa[id].rs = 0;
}
else
{
printf("-1\n");
}
}
}
return 0;
}
總之，沒有完美的數據結構。但左偏樹確實好寫，不想用堆了（直接用平板電視更容易）
