左偏树学习笔记 - Baoshuo's OI Blog

左偏树（Leftist Tree 或 Leftist Heap，又称左偏堆、左倾堆）是一种可以快速合并的可并堆，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中都有着广泛应用。

#定义

左偏树是一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针（left、right）外，还有两个属性：键值（value）和距离（dist，部分英文文献中称为 s-value）。键值用于比较节点的大小。距离的定义如下：

当且仅当节点 $x$ 的左子树或右子树为空时，节点被称作外节点（实际上保存在二叉树中的节点都是内节点，外节点是逻辑上存在而无需保存）。节点 $x$ 的距离是节点 $x$ 到它的后代中的最近的外节点所经过的边数。特别的，如果节点 $x$ 本身是外节点，则它的距离为 $0$ ；而空节点的距离规定为 $-1$ 。

#性质

节点的键值小于或等于它的左右子节点的键值。
节点的左侧子节点的 $\mathrm{dist}$ 值大于等于右子节点的 $\mathrm{dist}$ 值。
由 $2$ 可知，左偏树每个节点的 $\mathrm{dist}$ 值都等于其右子节点的 $\mathrm{dist}$ 值加 $1$ 。
树根的 $\mathrm{dist}$ 值不超过 $\lceil \log (n+1) \rceil - 1$ 。

#合并操作

合并两个堆时，由于要满足堆性质，先取值较小的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的 $\mathrm{dist}$ 值小于右儿子的 $\mathrm{dist}$ 值，就交换两个儿子。

In class LeftistTree<T>C++

static pointer_type merge(pointer_type x, pointer_type y) {
    if (!x) return y;
    if (!y) return x;

    if (x->val > y->val) std::swap(x, y);

    x->rchild = merge(x->rchild, y);

    if (!x->lchild || x->lchild->dist < x->rchild->dist) std::swap(x->lchild, x->rchild);

    x->dist = x->rchild ? x->rchild->dist + 1 : 0;

    return x;
}

#删除节点

删除操作直接将左右儿子进行合并即可。注意此处维护了一个指向父亲节点的指针。

In class LeftistTree<T>C++

static pointer_type merge(pointer_type x, pointer_type y) {
    if (!x) return y;
    if (!y) return x;

    if (x->val > y->val) std::swap(x, y);

    x->rchild = merge(x->rchild, y);

    if (!x->lchild || x->lchild->dist < x->rchild->dist) std::swap(x->lchild, x->rchild);

    if (x->lchild) x->lchild->root = x;
    if (x->rchild) x->rchild->root = x;

    x->dist = x->rchild ? x->rchild->dist + 1 : 0;

    return x;
}

void erase() {
    if (lchild) lchild->root.reset();
    if (rchild) rchild->root.reset();

    root = merge(lchild, rchild);
}

#代码实现

下面一个封装好的左偏树模板，支持泛型和自定义比较器，内部使用了智能指针来简化内存管理。

C++

#include <functional>
#include <memory>
#include <stack>

template <typename T, class Compare = std::less<T>>
class LeftistTree : public std::enable_shared_from_this<LeftistTree<T, Compare>> {
  public:
    using pointer_type = std::shared_ptr<LeftistTree<T, Compare>>;

  protected:
    static Compare comp;

  private:
    size_t dist;
    pointer_type lchild, rchild;
    std::weak_ptr<LeftistTree<T, Compare>> root;

  public:
    T val;

    LeftistTree(const T& _val = 0)
        : dist(0),
          lchild(nullptr),
          rchild(nullptr),
          root(),
          val(_val) {}

    pointer_type find_root() {
        std::stack<pointer_type> st;
        pointer_type cur = this->shared_from_this();

        st.emplace(cur);

        while (auto ptr = cur->root.lock()) {
            st.emplace(cur = ptr);
        }

        st.pop();

        while (!st.empty()) {
            auto ptr = st.top();
            st.pop();

            ptr->root = cur;
        }

        return cur;
    }

    void erase() {
        if (lchild) lchild->root.reset();
        if (rchild) rchild->root.reset();

        root = merge(lchild, rchild);
    }

    static pointer_type merge(pointer_type x, pointer_type y) {
        if (!x) return y;
        if (!y) return x;

        if (comp(x->val, y->val)) std::swap(x, y);

        x->rchild = merge(x->rchild, y);

        if (!x->lchild || x->lchild->dist < x->rchild->dist) std::swap(x->lchild, x->rchild);

        if (x->lchild) x->lchild->root = x;
        if (x->rchild) x->rchild->root = x;

        x->dist = x->rchild ? x->rchild->dist + 1 : 0;

        return x;
    }
};