`
liuxinyu95
  • 浏览: 30120 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

二项式堆、斐波纳契(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
分享到：
| AVL tree，比红黑树更朴素
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    斐波纳契数列求和算法

    c# 斐波纳契数列求和算法 的实现。

    斐波纳契时钟

    先科普一下斐波那契这个“销魂”的词语吧，它是一个数学序列名称，从该数列的第二项开始，为前两项的加和（第二项和第一项相等），例如：1、1、2、3、5、8、13......就是一种斐波那契数列。该斐波那契时钟就是依照...

    论文研究-基于DWT-SVD和Fibonacci变换的彩色图像盲水印算法.pdf

    为提高水印鲁棒性, 将离散小波变换DWT、奇异值分解SVD和斐波纳契Fibonacci变换结合, 提出一种新的算法。首先, 用Fibonacci变换对拟嵌入的水印进行置乱处理; 然后, 对宿主彩色图像R、G、B三个分量进行二级小波变换和...

    算法导论（中文 第二版）答案

    　第二十章 斐波纳契堆（Fibonacci Heaps） 　第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets） 　第六部分（Part VI） 图算法（Graph Algorithms） 　第二十二章 基本的图算法（Elementary ...

    斐波纳契数列

    斐波纳契数列的简单实现， 1，1，2，3，5，8，13，21，34，55，89……这个数列则称为“斐波纳契数列”，其中每个数字都是“斐波纳契数”。

    矩阵乘法求斐波纳契数列

    矩阵快速幂的模板 ，采用矩阵转移的方法求斐波纳契数列的第n项。

    java斐波纳契数列

    The Fibonacci numbers Fn are defined as follows: F0 is 1, F1 is 1, and Fi+2 = Fi + Fi+1 , where i = 0, 1, 2, . . . . In other words, each number is the sum of the previous two numbers. The first few ...

    斐波那契数列java的简单实现

    斐波那契数列java的简单实现，很简单明了

    Python——Fibonacci数列生成

    此后的每一项都是前两项的加和，根据这个规律，可以利用Python编写简单的程序来实现输出指定的n位斐波那契数字，代码如下： ''' @Author: FangChur @Date: 2020-04-03 10:19:27 @LastEditTime: 2020-04-03 10:51:20...

    算法导论（第2版）参考答案

    　第二十章 斐波纳契堆（Fibonacci Heaps） 　第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets） 　第六部分（Part VI） 图算法（Graph Algorithms） 　第二十二章 基本的图算法（Elementary ...

    实现斐波纳契数列求和

    实现斐波纳契数列求和，。程序完全可以实现运行，希望可以帮助大家

    算法导论（原书第二版）

    第二十章 斐波纳契堆（Fibonacci Heaps） 第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets） 第六部分（Part VI） 图算法（Graph Algorithms） 第二十二章 基本的图算法（Elementary Graph ...

    算法导论-第三版(中文).rar

    第二十章 斐波纳契堆（Fibonacci Heaps） 第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets） 第六部分（Part VI） 图算法（Graph Algorithms） 第二十二章 基本的图算法（Elementary Graph ...

    python 斐波纳契数列

    python 斐波纳契数列

    斐波那契数列的求解

    斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、...

    算法导论第三版英文原版

    第二十章 斐波纳契堆（Fibonacci Heaps） 第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets） 第六部分（Part VI） 图算法（Graph Algorithms） 第二十二章 基本的图算法（Elementary Graph ...

    算法导论（英文版）

    第二十章 斐波纳契堆（Fibonacci Heaps） 第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets） 第六部分（Part VI） 图算法（Graph Algorithms） 第二十二章 基本的图算法（Elementary Graph ...

Magicbox
Global site tag (gtag.js) - Google Analytics