IOI2005国家集训队论文 黄源河

作的时间复杂度可能退化为O(n)，不过通常这并不影响算法的总时间复杂度。

总的来说，斜堆作为左偏树的变种，与左偏树并无优劣之分。在斜堆能派上用场的地方，左偏树同样能出色地实现算法。斜堆与左偏树之间的关系，可以类比于伸展树与AVL树之间的关系，只不过前两者的编程复杂度，并没有多大的差别。

5.2 左偏树与二叉堆的比较

二叉堆大概是我们最常用的一种优先队列了，它具有简洁，高效的特点，应用十分广泛。二叉堆和左偏树相比，除了合并操作外的各种操作，时间复杂度都一样，但在实际测试中，二叉堆往往比左偏树快一些。在空间上，由于二叉堆是完全二叉树，用数组表示法，可以剩下左右子树指针的空间，在这点上左偏树又吃了一亏。

介绍了二叉堆的优点，下面的这两个缺点也是不容忽视的：

1．在进行插入、删除等操作后，二叉堆中元素的物理位置会发生改变。 2．二叉堆的合并操作太慢，时间复杂度高达O(n)。

当元素本身所占空间比较大时，频繁地移动元素物理位置将会影响时间效率。而有些时候，我们需要随时掌握某些元素的物理位置，以便对它进行访问或修改（比如实现删除任意已知节点操作），这时，二叉堆的第一个缺点将给我们造成一定的麻烦，我们不得不通过增加元素指针等手段来解决这个问题。而二叉堆合并效率的低下则是由其本身性质所造成的，采用启发式合并可以作为大多数情况下的一个优化，但效果仍不能令人满意。

至于二叉堆空间上的优势，也不是绝对的。数组表示法并不是在任何场合都适用的，比如当我们需要动态维护多个优先队列的时候，二叉堆不得不使用传统的指针表示法，这时二叉堆和左偏树在空间上就相差无几了。

二叉堆的上述特点，决定了它不适合作为可并堆的实现。客观的说，需要实现可并堆的题目在竞赛中并不多见，不过当我们遇到这类题目或者某些特殊的情况时，左偏树将会是比二叉堆更好的选择。

5.3 左偏树与其他可并堆的比较

前面已经提到过，可并堆可以用多种数据结构实现，左偏树并非唯一的选择。二项堆，Fibonacci堆都是时间效率十分优秀的可并堆。

二项堆是由若干棵深度不同的二项树组成的森林。深度为k的二项树Bk由两棵二项树Bk-1连接根节点而成，有2k个节点，并且满足堆性质。二项树组成二项堆的形式可以看作总节点数n的二进制表示形式，两个二项堆的合并可以看作二进制数的加法，这点很有启发意义。与左偏树类似，二项堆的各种操作也是在合并操作的基础上完成的。二项堆的结构和性质决定了它可以很高效地完成合

第 16 页 共 21 页

IOI2005国家集训队论文 黄源河

并操作，与左偏树相比，虽然复杂度相同，但一般实际情况下二项堆比较快。但二项树实现取最小节点操作需要检查所有二项树的根节点，因此这项操作时间复杂度比左偏树高*。

Fibonacci堆是一个很复杂的数据结构，与二项堆一样，它也是由一组堆有序的树构成的。所不同的是，Fibonacci堆的树不一定是二项树，而且这些树是无序的，且树中兄弟节点的联系用双向循环链表来表示。Fibonacci堆实现插入操作和合并操作只是简单地将两个Fibonacci堆的根表连在一起，因此这两个操作比其他可并堆都快。但在删除操作时，我们需要对Fibonacci堆进行维护，合并所有度数相同的树，这一步异常复杂，并且是最慢的。

有关二项堆和Fibonacci堆的详细介绍，有兴趣的读者可以参考相关资料，本文不再赘述。下表列出了各种可并堆的各项操作的时间复杂度?，已及它们的空间需求和编程复杂度。

项目 二叉堆 左偏树 二项堆 Fibonacci堆 构建 O(n) O(n) O(n) O(n) 插入 O(logn) O(logn) O(logn) O(1) 取最小节点 O(1) O(1) O(logn) O(1) 删除最小节点 O(logn) O(logn) O(logn) O(logn) 删除任意节点 O(logn) O(logn) O(logn) O(logn) 合并 O(n) O(logn) O(logn) O(1) 空间需求 最小 较小 一般 较大 编程复杂度 最低 较低 较高 很高 从表中我们可以看出，Fibonacci堆的时间复杂度非常低，如果我们不需要进行频繁的删除操作，用Fibonacci堆实现可并堆将会降低算法的时间复杂度。但实际上，删除操作往往是很重要的操作，而Fibonacci堆的删除操作比表中其它可并堆都慢，至于它的空间需求，也大得使人望而却步。更槽糕的是Fibonacci堆的编程复杂度太高了，在竞赛中使用实在是不理智的行为。

至于二项堆，虽然各项操作的时间效率都十分优秀，但空间需求和编程复杂度仍然比不上左偏树。和左偏树相比，二项堆在时间效率上的优势微乎其微，用左偏树代替二项堆，的确会牺牲一些算法性能，但换来的却是简洁的代码，便于实现和调试的程序。在时间有限的竞赛中，左偏树无疑是更好的选择。

最后，我们应该认识到，虽然二项堆和Fibonacci堆某些操作的时间复杂度比左偏树低，但是在实际应用中，那些时间复杂度较高的操作往往会成为算法的瓶颈。比如前面的例题《数字序列》，改用二项堆或Fibonacci堆实现，总时间复杂度仍为O(nlogn)，并不能起到降低算法时间复杂度的作用，实现难度反而增加了不少。

*

这里其实有一个办法可以解决这个问题，就是随时记录最小节点，并只在插入、删除以及合并等操作进行的时候更新该记录，这样二项堆的取最小节点操作时间复杂度可以降为O(1) ?

表中Fibonacci堆的“删除最小节点”和“删除任意节点”两个操作的时间复杂度均为平摊时间复杂度，而二项堆“插入”操作的平均时间复杂度为O(1)，表中给出的是最坏时间复杂度

第 17 页 共 21 页

IOI2005国家集训队论文 黄源河

六、总结

至此，我们已经对左偏树有了深刻的认识。左偏树在时间效率上不如二项堆和Fibonacci堆，在空间效率上不如二叉堆，这样看来左偏树没有任何独树一帜的地方，似乎是个相当平庸的数据结构，但其实这正是左偏树的优势所在。正所谓“鱼与熊掌不可兼得”，时间复杂度、空间复杂度和编程复杂度，这三者之间很多时候是矛盾的。Fibonacci堆时间复杂度最低，但编程复杂度让人无法接受；二叉堆的空间复杂度和编程复杂度都很低，但时间复杂度却是它的致命弱点。左偏树很好地协调了三者之间的矛盾，并且在存储性质上，没有二叉堆那样的缺陷，因此左偏树的适用范围十分广。左偏树不但可以高效方便地实现可并堆，更可以作为二叉堆的替代品，应用于各种优先队列，很多时候甚至比二叉堆更方便。

【感谢】

感谢余江伟同学及阮志远老师的热心帮助和修改意见。

【参考文献】

[1] 傅清祥，王晓东 算法与数据结构（第二版） 电子工业出版社

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

Introduction to Algorithms (Second Edition) The MIT Press [3] Mark Allen Weiss Data Structures and Algorithm Analysis in C (Second

Edition) Pearson Education

第 18 页 共 21 页

IOI2005国家集训队论文 黄源河

【附录】

附录I ：例题《数字序列》的原题

SEQUENCE

Short formulation. The number sequence is given. Your task is to construct the increasing sequence that approximates the given one in the best way. The best approximating sequence is the sequence with the least total deviation from the given sequence.

More precisely. Let t1, t2, …, tN is the given number sequence. Your task is to construct the increasing number sequence z1 < z2 < …< zN .

The sum |t1 - z1| + |t2 - z2| + … + |tN - zN| should be a minimal feasible.

Input

There is the integer N (1≤N≤1000000) in the first line of input file seq.in. Each of the next N lines contains single integer – the given sequence element. There is tK in the (K+1)-th line. Any element is satisfying to relation 0≤tK≤2000000000.

Output

The first line of output file seq.out must contain the single integer – the minimal possible total deviation. Each of the next N lines must contain single integer – the recurrent element of the best approximating sequence.

If there are several solutions, your program must output any one sequence with a least total deviation.

Example

seq.in 7 9 4 8 20 14 15 18

seq.out 13 6 7 8 13 14 15 18 第 19 页 共 21 页

IOI2005国家集训队论文 黄源河

附录II ：例题《数字序列》左偏树解法的程序

PROGRAM Seq_LeftistTree; TyPe node= record dist:byte;

key,left,right:longint; end; VaR

nd:array[0..1000000]of node; stk,q:array[0..1000000]of longint; n,cl,i:longint;

Function merge(a,b:longint):longint; var

c:longint; begin

if (a=0)or(b<>0)and(nd[a].key

if b=0 then exit;

nd[a].right:=merge(nd[a].right,b);

if nd[nd[a].left].dist

c:=nd[a].left;

nd[a].left:=nd[a].right; nd[a].right:=c; end;

nd[a].dist:=nd[nd[a].right].dist+1; end;

Procedure print; var

tot,i,j:longint; begin tot:=0;

for i:=1 to cl do

for j:=q[i-1]+1 to q[i] do

inc(tot,abs(nd[j].key-nd[stk[i]].key)); writeln(tot); end;

第 20 页 共 21 页