二项式堆、斐波纳契据(Fibonacci)堆和Pairing堆

二项式堆、斐波纳契(Fibonacci)堆和Pairing堆
通常的数据结构和算法教科书介绍的堆，实际上是用数组隐式表达的二叉树堆（binary heap by implicit array），如果将概念扩展为多叉树或者森林，就会得到更多有趣的堆。本章介绍的3种堆，就是其中很有代表性的数据结构。

其中二项式堆把合并的速度提高到了O(lg N)的量级，如果把二项式堆的某些操作延迟进行，就得到了Fibonacci堆，Fibonacci堆的各项指标除了pop外，都达到了O(1)的量级，在理论上的意义特别重大。它使得诸多的图算法，如Dijkstra算法等得以高效实现。

遗憾的是Fibonacci Heap的实现有些复杂，时间常数比较大，理论意义大于实际意义。为此本章最后介绍了Pairing Heap，一种实现起来非常简单，并且效率很高的Heap。然而从它发明至今的15年内，没有人能给出它复杂度的严格证明。

本章所有的算法都给出了Functional实现和imperative实现，并附有Haskell, ANSI C和Python的源代码。

本章原稿和全部代码在FDL和GPL许可证下开源：
PDF文件：https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
https://github.com/liuxinyu95/AlgoXY