dist 的性質

對于一棵二叉樹，我們定義左孩子或右孩子為空的節點為外節點，定義外節點的?distdist?為?11，空節點的?distdist?為?00，不是外節點也不是空節點的?distdist?為其到子樹中最近的外節點的距離加一。
一棵根的?distdist?為?xx?的二叉樹至少有?2x?12x?1?個節點。此性質所有二叉樹都有，并非左偏樹特有。
distdist?不是深度，左偏樹的深度沒有保證，一條向左的鏈也是左偏樹。

左偏樹的性質

左偏樹是一棵二叉樹，并且是“左偏”的，即每個節點左兒子的?distdist?都大于等于右兒子的?distdist。
因此，左偏樹中每個節點的?distdist?是它右兒子的?distdist?加一。

變量

int lson[N], rson[N], fa[N], fat[N];
ll val[N], dist[N];

lson: 左孩子（左偏）；
rson: 右孩子；
fa: 父節點；
fat: 祖先（并查集）；
val: 權值；
dist: 就是?distdist。

操作

• 合并

int merge(int x, int y) { // 合并if (!x || !y) {return x | y;}if (val[x] > val[y] || (val[x] == val[y] && x > y))swap(x, y);rson[x] = merge(rson[x], y);fat[rson[x]] = fa[rson[x]] = x;if (dist[lson[x]] < dist[rson[x]])swap(lson[x], rson[x]);dist[x] = dist[rson[x]] + 1;return x;
}

if (!x || !y) { return x | y; }
如果與空節點合并，則直接合并即可
if (val[x] > val[y] || (val[x] == val[y] && x > y))
說明這是個小根堆，小元素在上面。
if (dist[lson[x]] < dist[rson[x]]) swap(lson[x], rson[x]);
維護左偏的性質。

• 刪除任意一個節點

左偏樹是不支持刪除給定權值的點的，只能刪除知道點的標號的點。

void earse(int u) { // 刪除任意一點int tmp = merge(lson[u], rson[u]), fu = fa[u];fat[tmp] = fa[tmp] = fu;fat[u] = fa[u] = tmp;lson[fu] == u ? lson[fu] = tmp : rson[fu] = tmp;while (fu) {if (dist[lson[fu]] < dist[rson[fu]])swap(lson[fu], rson[fu]);if (dist[fu] == dist[rson[fu]] + 1)return ;dist[fu] = dist[rson[fu]] + 1;fu = fa[fu];}
}

int tmp = merge(lson[u], rson[u]), fu = fa[u];?先將被刪節點的左右孩子合并。
fat[tmp] = fa[tmp] = fu;?處理好父親和孩子的關系。

while (fu) {if (dist[lson[fu]] < dist[rson[fu]])swap(lson[fu], rson[fu]);if (dist[fu] == dist[rson[fu]] + 1)return ;dist[fu] = dist[rson[fu]] + 1;fu = fa[fu];
}

刪除點之后可能不符合左偏性質，需要我們向上修改，直到到根節點或符合左偏性質為止。

• 查詢?uu?點所在堆的堆頂元素的標號

這個操作類似于并查集操作。

int find(int u) { // 查詢堆頂的元素的標號return (fat[u] == u || fat[u] == 0) ? u : fat[u] = find(fat[u]);
}

• 刪除?uu?點所在堆的堆頂元素

void pop(int u) { // 彈出 u 點所在對的堆頂元素int g = find(u);earse(g);
}

• 查詢?uu?點所在堆的堆頂元素

ll top(int u) { // 查詢 u 點所在堆的堆頂元素int g = find(u);return val[g];
}

• 建樹操作

int build(int n) { // 建樹queue<int> q;for (int i = 1; i <= n; ++ i) {q.push(i);}int x, y, z;while (q.size() > 1) {x = q.front(), q.pop();y = q.front(), q.pop();z = merge(x, y), q.push(z);}return q.front();
}

模板

// 左偏樹（小根堆）
struct leftist_tree {int lson[N], rson[N], fa[N], fat[N];ll val[N], dist[N];int merge(int x, int y) { // 合并if (!x || !y) {return x | y;}if (val[x] > val[y] || (val[x] == val[y] && x > y))swap(x, y);rson[x] = merge(rson[x], y);fat[rson[x]] = fa[rson[x]] = x;if (dist[lson[x]] < dist[rson[x]])swap(lson[x], rson[x]);dist[x] = dist[rson[x]] + 1;return x;}int find(int u) { // 查詢堆頂的元素的標號return (fat[u] == u || fat[u] == 0) ? u : fat[u] = find(fat[u]);}void earse(int u) { // 刪除任意一點int tmp = merge(lson[u], rson[u]), fu = fa[u];fat[tmp] = fa[tmp] = fu;fat[u] = fa[u] = tmp;lson[fu] == u ? lson[fu] = tmp : rson[fu] = tmp;while (fu) {if (dist[lson[fu]] < dist[rson[fu]])swap(lson[fu], rson[fu]);if (dist[fu] == dist[rson[fu]] + 1)return ;dist[fu] = dist[rson[fu]] + 1;fu = fa[fu];}}ll top(int u) { // 查詢 u 點所在堆的堆頂元素int g = find(u);return val[g];}void pop(int u) { // 彈出 u 點所在對的堆頂元素int g = find(u);earse(g);}int build(int n) { // 建樹queue<int> q;for (int i = 1; i <= n; ++ i) {q.push(i);}int x, y, z;while (q.size() > 1) {x = q.front(), q.pop();y = q.front(), q.pop();z = merge(x, y), q.push(z);}return q.front();}
};

pb_ds 中的堆

__gnu_pbds :: priority_queue?

成員函數

?

push(): 向堆中壓入一個元素，返回該元素位置的迭代器。
pop(): 將堆頂元素彈出。
top(): 返回堆頂元素。
size(): 返回元素個數。
empty(): 返回是否非空。
modify(point_iterator, const key): 把迭代器位置的?key?修改為傳入的?key，并對底層儲存結構進行排序。?
erase(point_iterator): 把迭代器位置的鍵值從堆中擦除。
join(__gnu_pbds :: priority_queue &other): 把?other?合并到?*this?并把?other?清空。