`
liuxinyu95
  • 浏览: 30875 次
  • 性别: 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，比红黑树更朴素
评论
发表评论

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

相关推荐

    斐波纳契数列求和算法

    这个数列的定义是：第一项F0为0，第二项F1为1，之后的每一项Fi（i >= 2）都是前两项之和，即Fi = Fi-1 + Fi-2。数列的初始几项是0, 1, 1, 2, 3, 5, 8, 13, ...。斐波纳契数列在自然界、艺术、音乐和许多科学领域都...

    实现斐波纳契数列求和

    简单来说，斐波纳契数列的每一项都是前两项的和。数列的前几项是0, 1, 1, 2, 3, 5, 8, 13, ...。 实现斐波纳契数列求和的程序通常是为了计算特定数列项的和或者展示递归或动态规划的概念。以下是一些常见的实现方法...

    斐波纳契数列

    数列的每一项都是前两项之和，通常以0和1开始，即F(0) = 0，F(1) = 1。接下来的数列就会按照这个规则发展：F(2) = 1，F(3) = 2，F(4) = 3，F(5) = 5，F(6) = 8，依此类推。这个数列在自然界、艺术、科学以及计算机...

    斐波纳契时钟

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

    斐波纳契数列编程解决方法

    这个数列的定义是这样的：第一项F0为0，第二项F1为1，从第三项开始，每一项都等于前两项之和。即Fn = Fn-1 + Fn-2 (n >= 3)。斐波那契数列在编程中的应用广泛，例如用于测试算法效率、数据结构优化等。 在C++中，有...

    斐波纳契回调线支撑与阻力分析系统

    斐波纳契回调线的理论基础源于数学上的斐波那契数列，这个数列由0和1开始，后续每个数字是前两个数字之和（1, 1, 2, 3, 5, 8, 13, ...）。斐波纳契数列在自然界和金融市场中都展现出惊人的规律性。在价格走势中，...

    矩阵乘法求斐波纳契数列

    矩阵快速幂的模板 ，采用矩阵转移的方法求斐波纳契数列的第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 ...

    算法导论（原书第二版）

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

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

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

    Python——Fibonacci数列生成

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

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

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

    k阶斐波那契序列C++程序（循环队列）

    斐波那契序列是一种在计算机科学和数学中广泛使用的数列，它的定义是：第一项F0通常是0，第二项F1通常是1，之后的每一项Fn都是前两项Fn-1和Fn-2的和。这个序列在自然界、算法设计和金融建模等多个领域都有重要应用。...

    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*）在现代物理、准晶体结构、...

    算法导论Introduction to Algorithms

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

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