左偏堆

介绍

一种可高效合并的堆结构，具有以下性质：

• 堆序性：任意节点值 $\geq$（或 $\leq$）子节点值。
• 左偏性：$dist_l \geq dist_r$

直观上左边比右边伸得长

$dist$标记

定义

dist表示某个节点到空节点的最短距离

• 空节点 $dist = -1$
• 叶节点 $dist = 0$
• 非叶节点 $dist = min(dist_l, dist_r)+ 1$

左偏树性质

根据左偏性（$dist_l \geq dist_r$），可知每个节点的 $dist$ 均来自右子树

• 即 $dist = dist_r + 1$

存储

不是完全二叉树，不适合顺序存储，但可以使用数组模拟链式存储，维护如下信息：

• $dist$：节点到空节点的最短距离
• $val$：节点值
• $l$：左子节点
• $r$：右子节点
• $fa$：父节点（可选）
• $del$：懒删除标记（可选）

如果你足够闲，也可以维护一个队列，美其名曰对象池，删除后的节点可以复用，稍微减少点空间开销（蚊子腿）

struct LeftHeap{
    struct Node{
        int dist = 0, val = 0; // 也许要用 long long
        int l = 0, r = 0, fa = 0;
        bool del = false;
        Node(int val): val(val) {}
    };
    vector<Node> tr;
    queue<int> pool; // 可复用队列，bro认为把它叫对象池显得高级
    LeftHeap() {
        tr.emplace_back(0);
        // 空节点 dist 设为 -1
        tr[0].dist = -1;
    }
};

合并操作（核心）

步骤

• 检查两个堆的根节点是否为空
• 比较两个堆的根节点，维护堆序性
• 递归合并至右子树（顺便维护父指针）
• 回溯维护左偏性并更新 $dist$

代码

int merge(int x, int y){
    // 任意一个为空，返回另一个
    if(!x || !y) return x | y;
    // 取较小的作为新根（设置为x）
    if(tr[x].val > tr[y].val) swap(x, y);
    // 合并堆到新根右子树
    tr[x].r = merge(tr[x].r, y);
    // 维护父指针
    if(tr[x].r) tr[tr[x].r].fa = x;
    // 维护左偏性，如果左树dist小于右树，交换左右子树
    if(tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
    // 更新新根dist = 新根右子树dist + 1
    tr[x].dist = tr[tr[x].r].dist + 1;
    // 堆顶无父节点
    tr[x].fa = 0;
    return x;
}

次级操作

插入

• 把插入元素看成单点堆
• 合并单点堆到主堆

int insert(int root, int val){
    // 如果用了对象池，就在这看下有没有能用的，不演示了
    // 新建单点堆，叶子节点 dist = 0   
    tr.emplace_back(val);
    // 合并单点堆到主堆
    return merge(root, tr.size() - 1);
}

弹出

• 合并根节点的左右子树
• 检查新根是否有删除标记
• 清空新根的父节点

int pop(int root){
    // 合并左右子树
    root = merge(tr[root].l,  tr[root].r);
    // 检查懒删除
    if(root && tr[root].del) root = pop(root);
    // 清空新根的父节点
    if(root) tr[root].fa = 0;
    // 返回新根
    return root;
}

删除

懒删除

• 设置删除标记
• 等pop()时再真的删掉

void del(int root){
    tr[root].del = true;
}

结构性删除

如果用这个方法就不用维护懒删除标记了

• 合并删除元素的左右子树
• 新根代替原有节点
• 维护左偏性
  • 左树 $dist$ 小则交换左右子树
  • 向上递归维护直到无需更新或到顶

void fix(int x){
    int &l = tr[x].l, &r = tr[x].r;
    // 检查是否需要交换
    if(tr[l].dist < tr[r].dist) swap(l, r);
    // 向上递归维护
    if(x && tr[x].dist != tr[r].dist + 1){
        tr[x].dist = tr[r].dist + 1;
        fix(tr[x].fa);
    }
}
int remove(int x){
    // 无父节点，跟 pop()一样了（记得写不带懒标记的 pop）
    // 这里很重要，如果不写就要在下面特判 fa = 0 的情况
    if(!tr[x].fa) return pop(x);
    // 合并左右子树
    int root = merge(tr[x].l,  tr[x].r);
    // 替代原有节点
    int fa = tr[x].fa;
        // 更换父节点的子指针
        if(tr[fa].l == x) tr[fa].l = root;
        else if(tr[fa].r == x) tr[fa].r = root;
        // 连接父节点（不为空）
        if(root) tr[root].fa = fa;
    // 从父节点向上维护左偏性
    fix(fa);
    return root;
}

修改

值修改

只修改节点的值，可能会引起编号变化，配合并查集时不建议使用

上浮下沉

• 修改单点值不影响左偏堆结构
• 类似二叉堆的上浮下沉，只交换值

void pushup(int x){
    int fa = tr[x].fa;
    // 没到顶且不满足堆序性
    while(fa && tr[fa].val > tr[x].val){ 
        // 交换值   
        swap(tr[x].val, tr[fa].val);
        // 继续向上
        x = fa, fa = tr[x].fa;
    }
}
void pushdown(int x){
    while(1){
        int l = tr[x].l, r = tr[x].r;
        // 取左右儿子中较小的设为l（不为空）
        if(!l || (r && tr[l].val > tr[r].val)) swap(l, r);
        // 没到底且不满足堆序性，交换值
        if(l && tr[l].val < tr[x].val) swap(tr[l].val, tr[x].val);
        // 否则可以结束
        else break;
        // 没结束就继续向下
        x = l;
    }
}

修改

• 修改单点值
• 维护堆序性
  • 破坏上部堆序性，上浮
  • 破坏下部堆序性，下沉

void modify(int x, int k){
    // 修改单点值
    tr[x].val = k;
    // 维护堆序性
    // 可以判断一下具体需要哪个，不过空跑一个也行
    pushup(x);
    pushdown(x);
}

移除重插

• 先把待更改元素移除
• 修改后重新插入

void modify(int x, int k){
    // 找到 x 所在的堆顶（配和并查集，不演示了）
    int root;
    // 如果 x 是堆顶，移除后堆顶会变
    if(!tr[x].fa) root = remove(x);
    // 不是堆顶，直接修改
    else remove(x);
    // 修改后重新插入
    tr[x].val = k;
    root = merge(root, x);
}

查询

查询根节点的值

int query(int root){
    return tr[root].val;
}

并查集寻根

通常用一个并查集，记录数组中每个元素属于哪个堆，即记录每个元素的根节点

注意，并查集根节点和左偏堆顶是不同的，需要单独一个数组映射

• 并查集根：代表元
• 左偏堆顶：堆顶元素

DSU dsu;
LeftHeap heap;
// 并查集根 -> 堆顶 映射
vector<int> dsu2heap(n);
// 合并两个堆
void merge(int x, int y){
    // 找到堆根
    int rx = dsu.find(x);
    int ry = dsu.find(y);
    // 合并堆得到新根
    int root = heap.merge(dsu2heap[rx], dsu2heap[ry]);
    // 合并并查集
    dsu.unite(rx, ry);
    // 更新根节点映射
    dsu2heap[dsu.find(x)] = root;
}
// 删除堆顶
void pop(int x){
    // 找到堆顶
    int rx = dsu.find(x);
    // 删除堆顶得到新根
    int root = heap.pop(dsu2heap[rx]);
    // 更新根节点映射
    dsu2heap[rx] = root;
}

复杂度

时间复杂度

• 合并：$O(\log n)$
• 插入：$O(\log n)$
• 弹出：$O(\log n)$
• 删除：
  • 懒删除：均摊 $O(1)$
  • 结构性删除：$O(\log n)$
• 修改：$O(\log n)$
• 查询：$O(1)$
• 并查集寻根：均摊 $O(\alpha(n))$

空间复杂度

• 存储：$O(n)$
• 并查集：$O(n)$