优先队列

Published: by Creative Commons Licence

  • Tags:

左偏树

左偏树和最小堆非常类似,二者的构建时间均为$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$。

下面说一下左偏树的核心操作,合并两个左偏树。假设两个左偏树分别为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)$。