数据结构: 可合并堆-左偏树

---

来自维基百科

左偏树(英语: leftist tree或leftist heap), 也可称为左偏堆, 左倾堆, 是计算机科学中的一种树, 是一种优先队列实现方式, 属于可并堆.
左偏堆的合并操作的最坏情況复杂度为O(log n), 而完全二叉堆为O(n), 所以左偏堆适合基于合并操作的情形.

本文图片引自 图解数据结构(9)--左偏树

左偏树的结构和性质

左偏树是可以合并的二叉堆, 首先满足作为堆的基本性质:

• 树形结构
• 节点储存信息, 有优先级
• 每个节点的优先级大于其子节点的优先级

此外, 左偏树有一些额外的性质, 来保证它合并的效率.
左偏树的节点至少需要保存:

• 左右子树节点 lc, rc
• 该节点到 有空子节点的节点 的最短距离 h
• 优先级权值 w

有空子节点的节点, 就是指子节点数不为2的节点

除了堆的性质, 左偏树还满足 "左偏" 的性质, 这一点保证它的合并效率是O(log n)
即每个节点的左子节点的h不小于右子节点的h, 因而有 h[rt] = h[rc[rt]] + 1
下图即是一棵左偏树, 节点上即权值(优先级), 小根堆, 蓝色数字为h
(注意, 左偏树的左子树一定不小于右子树)

1.png

左偏树的操作

同样, 左偏树可以做到普通的堆可以做到的:

• 插入元素 O(log n)
• 查询最值 O(1)
• 删除堆顶 O(log n)

而且还可以做到额外的:

• 合并 O(log n)

并且, 插入和删除都是基于合并的:

• 插入即合并原树和一个新节点
• 删除即合并根的两个子树

左偏树的合并操作

以小根堆为例:
假如要合并两个堆 A, B
首先令 w[A] < w[B], 然后进行合并merge(A, B)
在该函数中:

• 如果 w[rc[A]] < w[B], merage(rc[A], B)
• 如果 w[rc[A]] > w[B], 交换 A的右子树 和 B, 然后继续merage(rc[A], B)
• 如果 A的右子树 或 B 为空, 则直接连接, 结束

如下图演示:

2-1.png 2-2.png 2-3.png 2-4.png

可以看得出来, 这一番操作后失去了左偏的性质, 所以还要在递归回溯的过程中维护左偏性质:
如果节点左子节点的h小于右子节点的h, 则交换左右子树, 维护该节点的h

2-5.png

合并操作的伪代码

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);

    /* 维护左偏性质 */
    if(h[lc[A]] < h[rc[A]]) swap(lc[A], rc[A]);

    /* 维护节点 A 的 h值 */
    if(rc[A] == NULL) h[A] = 0;
    else h[A] = h[rc[A]] + 1;

    return A;
}

完整代码

NODE_NUM 为最大节点数, 所有的树的节点都在lt数组里
若改成大根堆只需要修改结构体里为 w > k.w

• 新建一棵树: rt = new_node(w);
• 合并两棵树: rt = merge(rt, rt2);
• 插入新节点: rt = insert(rt, w);
• 删除根节点: 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;
}

//新建一个节点
int new_node(int w)
{
    lt[++cnt].w = w;
    lt[cnt].h = lt[cnt].rc = 0;
    return cnt;
}

//插入一个权值为w的节点
int insert(int A, int w)
{
    return merge(A, new_node(w));
}

//删除堆顶
int del(int A)
{
    return merge(lt[A].lc, lt[A].rc);
}