优先队列

Published: June 28, 2019 by Daltao

Categories:
algorithm 101

左偏树

左偏树

左偏树和最小堆非常类似，二者的构建时间均为 $O(n)$ ，可以以 $O(\log_2n)$ 的时间复杂度弹出最小元，以 $O(\log_2n)$ 时间复杂度插入新的元素。但是左偏树有一个能力是最小堆无法做到的，大小为n和m的两个左偏树合并，只需要 $O(\log_2nm)$ ，而最小堆使用启发式合并的思路也只能达到 $O(\min(n,m)\log_2(n+m))$ 。

左偏树的实现非常简单。每个左偏树结点拥有四个属性，左孩子、右孩子、关键字、距离。前三个属性和一般平衡树无异，第四个属性是什么呢？我们认为空结点的距离为-1，认为一个非空结点的距离为左右结点的距离中最小值加1。由于在堆中左右子结点没有大小关系，因此我们始终将左结点设为子结点中距离较大者，此时可以直接认为结点的距离为右子结点的距离加1。

命题1：只有n个结点的左偏树，其距离不可能超过 $\log_2n$ 。

我们记f(x)表示拥有x个结点的左偏数根节点距离的最大值。当n=1时，命题显然成立。假设当n<k时，命题始终成立。那么当n=k时，我们设左子树下有x个结点，右子树下的结点数为 $k-1-x$ 。

$f(k)=1+\min(f(x),f(k-1-x))\leq 1+f(\lfloor \frac{k-1}{2} \rfloor)\leq 1+\log_2\frac{k-1}{2}\leq \log_2k$

下面说一下左偏树的核心操作，合并两个左偏树。假设两个左偏树分别为a、b，不妨认为a的关键字不大于b的关键字。我们将b与a的右结点合并，之后维护a，保证a满足左偏树的特性（右子结点的距离不超过左子结点，同时a的距离等于右结点的距离加1）。

merge(a, b){
    if(a.key > b.key)
    {
        swap(a, b);
    }
    merge(a.right, b);
    if(a.right.distance > a.left.distance)
    {
        swap(a.left, a.right);
    }
    a.distance = a.right.distance + 1;
    return a;
}

由于每次递归，a、b中一个结点距离保持不变，一个结点的距离减少1，由于两个大小为n、m的左偏树的距离和不超过 $O(\log_2n+\log_2m)$ ，因此可以证明函数调用次数不会超过 $O(\log_2n+\log_2m)$ ，时间复杂度也是 $O(\log_2nm)$ 。

左偏树的删除最小元，我们只需要将根节点的左右子树合并即可。而插入新的元素，等价于创建一个只有单结点的左偏树，之后与原树合并即可。二者的时间复杂度均为 $O(\log_2n)$ 。

建图和最小堆一样，有线性的做法。首先将所有只有一个结点的左偏树放入到队列中。之后不断从队列头部弹出两个左偏树合并后加入到队列末尾。可以推出时间复杂度为 $\sum_{i=1}^{\log_2n}\frac{n}{2^i}(2\log_2i+1)$ 。这个求和式和建堆的一致，均为 $O(n)$ 。