Chapter 4 | Leftist Heap & Skew Heap

Leftist Heap

概述

我们不太满意 Binary Heap 的 Merge，因为全部打乱再 BuildHeap 的操作消解了两个 Heap 的特征，虽然说 \(O(n)\) 已经不错了，但是我们还想找到更好的结构来进行快速的堆合并操作，于是左偏堆 (Leftist Heap) 应运而生 , 它的堆合并操作的复杂度只要 \(O(log(n))\)

左偏堆 (Leftlist Heap) 也是一颗二叉树，不仅具有堆的性质，并且是 「左偏」 的，但是由于它并不再是一颗完全二叉树，所以不能像维护大小堆一样用数组来维护它

定义

一个左偏堆的结点维护了左右子堆的地址、自身的键值、和一个距离 (dist)/Npl(null path length)

struct LeftistHeapNode {
    ElementType val;
    int dist;
    LeftistHeapNode * ls, * rs;
};

性质

操作

左偏堆的核心操作就是合并。而其它操作都可以看作是合并的特殊情况。因此我们首先讨论任意两个左偏堆的合并。

合并

作为左偏堆的核心操作，合并操作自然就是要在满足性质的条件下，合并两个左偏堆。大致思路就是先维护堆的性质，在回溯时维护左偏性质，所以实际上它是一个先自上而下再自下而上的过程。

按照实现方法，左偏堆的合并可以分为递归式和迭代式两种。其中前者可能更为直觉，而后者可视化后则更为直观。

递归式

递归式先比较当前两个待合并子树的根结点的键值，选择较小（较大）的那个作为根结点，其左子树依然为左子树，右子树更新为「右子树和另一个待合并子树的合并结果」。

当然，在递归地更新完后，我们需要检查左子树和右子树是否满足 \(dist_\text{left child} \geq dist_\text{right child}\) 的性质，如果不满足，我们则需要交换左右子树来维持性质。

LeftistHeapNode * merge(LeftistHeapNode * x, LeftistHeapNode * y) {
    // Recursive exit. If any is NULL, return the other as the new root of subtree.
    if (x == NULL) return y;
    if (y == NULL) return x;

    // If `x`'s val is smaller than `y`'s, swap them, which means we always operates on `x`.
    if (x->val > y->val) {
        swap(x, y);
    }

    // Merge `x`'s right subtree and `y`, and set `x`'s right subtree to the result.
    x->rs = merge(x->rs, y);

    // If `x`'s left subtree's dist is smaller than `x`'s right subtree's dist, swap them.
    if (x->ls->dist == NULL || x->ls->dist < x->rs->dist) {
        swap(x->ls, x->rs);
    }

    // Update x's dist.
    x->dist = x->rs->dist + 1;

    // Return x as the new root of subtree.
    return x;
}

迭代式

迭代式是根据它的实现方法来命名的，但是我认为从可视化的角度来理解迭代式可能更有意思。事实上在很多题目中我觉得这个方法做题更加方便。

迭代式维护两个额外的指针，分别指向两棵树还没被合并的子树的根，并不断选择较小的那个合并进去，直到两个指针都为空。可以发现，这个过程和归并排序的后半部分非常相似，实际上当我们从可视化的角度去看这件事以后，会发现这里做的就是一个归并。

LeftistHeapNode * merge(LeftistHeapNode * x, LeftistHeapNode * y) {
    // `tx` & `ty` are the pointers to the roots of the subtrees that haven't been merged.
    LeftistHeapNode * tx = x, * ty = y;
    // `res` is the root of the merged final tree, while `cur` is the latest node that has been merged.
    LeftistHeapNode * res = NULL, * cur = NULL;

    // Begin merging.
    whie (tx != NULL && ty != NULL) {
        // If `tx`'s val is smaller than `ty`'s, swap them, which means we always operates on `tx`.
        if (tx->val > ty->val) {
            swap(tx, ty);
        }

        // Specially mark the root on the first merge.
        if (res == NULL) {
            res = tx;
            cur = tx;
        } else {
            cur->rs = tx;
            cur = cur->rs;
        }

        // Go on.
        tx = tx->rs;
    }

    // Merge the rest of the tree.
    while (ty != NULL) {
        // Specially mark the root on the first merge. (rarely happens but not impossible)
        if (res == NULL) {
            res = ty;
            cur = ty;
        } else {
            cur->rs = ty;
            cur = cur->rs;
        }

        // Go on.
        ty = ty->rs;
    }

    // Adjust the left and right subtrees of all the nodes according to the properties of `dist`. 
    // It does the same work as the adjust part in the recursive version. I ignore it here.
    res = adjust(res);

    return res;
}

依旧是以上面进行模拟的那个合并为 🌰 进行模拟。

在做左斜堆合并的题目时，个人比较喜欢迭代式的做法，只需要沿着最右路径把每个左子树写出来再排序，最后沿着最右路径连回来即可（当然最后还要沿着最右路径对 dist 进行维护）

再次提醒，这一小节讲的部分都忽略了之后调整子树左偏性质的过程，实际上这也就单纯是一个维护堆性质的过程 -- 只需要对最右路径 Top-Down 或者 Bottom-Up 进行维护即可

插入

插入可以直接看作是和只有一个根节点的树的合并

删除

删除操作也比较简单，只需要对被删除节点的两个孩子做合并操作即可

这里贴一段代码方便理解

LeftistHeapNode * del(LeftistHeapNode * cur, ElementType x) {
    if (cur->val == x) {
        // Just return the merge of the children.
        return merge(cur->l, cur->r);
    } else {
        // Not this subtree.
        if (cur->val > x) return cur;

        // Otherwise, search the `x`.
        if (cur->l != NULL) del(cur->l, x);
        if (cur->r != NULL) del(cur->r, x);

        // Adjust the dist bottom-up.
        adjust(cur);
    }
}

Skew Heap

概述

Skew Heap 其实是 Leftist Heap 的一种自适应版本，它们二者之间的关系就类似于 AVL Tree 和 Splay Tree 的关系（事实上，发明 Skew Heap 的人和发明 Splay Tree 的人是同一个人）

Skew Heap 是一种具有堆性质的二叉树，但是并没有像 Leftist Heap 一样的对结构上的限制，并没有诸如 Npl 这样的信息存储在各个节点上，这也就意味着一个 Skew Heap 的 Right Path 可能会非常长，这导致了所有操作的最坏时间复杂度是 \(O(n)\) 级别的，但是就像 Spaly Tree 一样，所有操作在摊还意义下的时间复杂度是 \(O(logn)\) 级别的

合并

斜堆也需要满足大根堆（小根堆）的性质，而它的合并和左偏堆的合并也十分类似，只不过我们这次无条件的交换左右子树，换句话来说，不管左偏性质如何变化，我们都会选择交换参与合并的左右子树，这样我们就不需要在回溯的时候才进行左右子树的交换，于是就实现了完全的自上而下。

让我们来看看 wiki 里给出的 🌰：

大概的操作类似是每次先比较两个子树的根节点大小，把大的子树往小的子树合并，具体合并过程是，将小的子树的左右子树交换，把新的左子树砍掉，让被砍掉的左子树和待合并的树合并后作为新的左子树 ;

如果遇到空节点和非空树合并时，若非空节点是该树唯一的最右路径节点，那么就不需要交换左右子树；否则交换左右子树。

当然，它也是支持迭代的写法的，和是和之前的做法类似，我们可以排序每一“条”，然后再合并。Wikipedia 上提供了一系列的过程图，但是那个过程图有点自下而上的意思，但是实际上自上而下做也是一样的。如果有兴趣可以去看看 Wiki 上的过程：🔗。

摊还分析

这里我们采用势能法分析摊还复杂度

分析 skew heap 的均摊复杂度，主要就是分析合并操作的复杂度，因为其他操作都可以转化为合并操作。

接下来我们需要定义势能函数：

其中，额外需要定义 heavy node 和 light node：

显然，对于 heavy node 和 light node，以及合并操作，有这么一些性质：

列出公式：

其中，\(c\) 为合并操作的（最坏）复杂度，\(H_{merged}\) 为合并后的堆的势能，\(H_x\) 和 \(H_y\) 分别为合并前的两个堆的势能。

根据 property 3，在合并过程中并非所有节点都收到影响。我们可以单独记录 \(l_{x}\) 为 \(H_x\) 最右侧路径上的 light node 数量，\(h_{x}\) 为 \(H_x\) 最右侧路径上的 heavy node 数量，\(h^0_{x}\) 为 \(H_x\) 所有不在最右侧路径上的 heavy node 数量（即 \(\text{count of heavy nodes of } H_x = H_x + H^0_x\)）。

于是，我们可以将上式写开：

其中稍微做一些解释：

1. \((1)\)：\(c\) 为合并操作的（最坏）复杂度，即我们的枚举涉及了两个堆所有的右侧路径；
2. \((2)\)：在合并操作以后，根据 property 1 和 property 2，可以得到这个不等式；
3. \((3)\) 和 \((4)\)：根据势能函数的定义得到；

于是，将它们代入得到结果：