📘
Introduction_to_Algorithms
  • Introduction
  • 第6章:堆排序
    • 练习题
    • 思考题
      • 6-3 Young
  • 第7章:快速排序
    • 练习题
    • 思考题
      • 7-6 对区间的模糊排序
  • 第8章:线性时间排序
    • 练习题
      • 8.3-4 O(n)时间内对[0..n^-1]之间的n个数排序
    • 思考题
      • 8-3 排序不同长度的数据项
  • 第9章 排序和顺序统计学算法导论
    • 练习题
      • 9.1-1
      • 9.3-3 快速排序-最坏时间O(nlgn)
      • 9.3-6 nlgk时间求k分位数
      • 9.3-8 求两个数组的中位数
    • 思考题
      • 9-2-c-带权中位数
  • 第10章:栈和队列
    • 10.1 栈和队列
      • 练习题
      • 10.1-2 用一个数组实现两个栈
      • 10.1-5 双端队列
    • 10.2 链表
      • 练习题
      • 10.2-5 环形链表实现字典操作INSERT、DELETE、SEARCH
    • 10.3 指针和对象实现
      • 练习题
      • 10.3-4 紧凑的多重数组
    • 思考题
  • 第11章 散列表
  • [第12章]
    • [笔记和代码]
      • 12-2 基数树
  • 第14章
    • 笔记和代码
      • 14.3-6 MIN GAP
  • 第15章:动态规划
    • 练习题
    • 思考题
      • 15-2 整齐打印
      • 15-3 编辑距离
  • 第20章:斐波那契堆
    • 练习题
    • 思考题
  • ACM解题报告
    • 1043 八数码问题
    • 1053 Entropy
    • 1114 Piggy-Bank 完全背包
    • 1133 catalan数二维变种
    • 1166 敌兵布阵
    • 1281 棋盘游戏 二分匹配与增广链
    • 1394 Minimum Inversion Number
    • 1394 用线段树求逆序数
    • 1787 欧拉函数之在线算法
    • 2438 三分查找
    • 2473 Junk-Mail Filter 并查集的删除
    • 2824 欧拉公式之打表算法
    • 2855 Fibonacci Check-up 矩阵的应用
    • 2642 Stars 二维树状数组
    • 2888 二维RMQ
    • 3033 分组背包之每组至少选一
    • 3307 A^B = C mod D,已知A,C,D,求解B
    • 3465 Life is a Line 用归并排序求逆序数
    • 3483 A Very Simple Problem 数论+矩阵的应用
    • 3518 后缀数组
    • 3579 中国剩余定理(ACM/不互质的情况)
    • 后缀数组
    • B-树
    • 排序算法总结
Powered by GitBook
On this page
  • 一、综述
  • 1.斐波那契堆
  • 2.斐波那契堆的结构
  • 3.可合并堆
  • 4.最大度数的界
  • 二、理解
  • 1.延迟合并操作
  • 2.合并调整操作
  • 3.mark的作用
  • 4.P300那句话
  • 三、改进
  • 1.命名
  • 2.分解函数
  • 3.合并函数
  • 4.参数和返回值
  • 5.功能
  • 四、代码

第20章:斐波那契堆

一、综述

1.斐波那契堆

斐波那契堆是可合并堆 在不涉及删除的操作(除去EXTRACT和DELETE)中,操作仅需O(1)的平摊运行时间 当EXTRACT和DELETE的操作数目较小时斐波那契堆能得到较好的运行效率。 斐波那契堆不能有效地支持SEARCH操作 用于解决诸如最小生成树和寻找单源最短路径等问题的快速算法都要用到斐波那契堆。

2.斐波那契堆的结构

斐波那契堆由一组最小堆构成,这些最小堆是有根的无序树。

  • 结点结构:

    key: 关键字,作为排序、判断结点大小的标准

    left, right:用于维护双链表,所有的根结点形成一个双链表,每个结点的孩子们形成双链表

    parent, child : 维护父子关系

    mark : 这个域与维护堆结构无关,只与具体的算法策略有关,不在这里讲

    degree: 记录该结点有几个孩子

  • 斐波那契堆

    n:堆中结点的个数

    min:批向最小的结点

3.可合并堆

引理19.1中给出的二项树的性质对无序二项树仍然成立P278 有n个结点FibHeap,结点的最大度数D(n) = lgn(向下取整) 将合并堆的操作尽可能地推后

4.最大度数的界

在一个包含n个结点的斐波那契堆中,结点的最大度数D(n)为O(lgn)

二、理解

1.延迟合并操作

FIB-HEAP-INSERT和FIB-HEAP-UNION只是最基础的链表合入操作,因为合并操作要尽可能地拖后 FIB-HEAP-EXTRACT-MIN除了要完成本职工作外,还要作合并调整

2.合并调整操作

CONSOLIDATE是作合并调整的函数 它将度数相同的根链接起来,直到对应每个度数至多只有一个根 遍历每一个根结点去判断,如果两个根结点的度是一样的,让大的结点作为小的结点的孩子

3.mark的作用

为了防止堆太宽,需要策略来调整堆,使根结点成为别的根结点的孩子,该策略就是CONSOLIDATE 同理,为了防止堆太深,也需要有相应的策略去调整,在适当的时候,把某个结点的孩子变成根 这一策略就是CUT和CASCADING-CUT,mark在实现这一策略的过程中起到辅助作用。 原理:当一个非根结点被切掉了2个孩子,就把它升为根结点 在删除一个结点时,怎么区分是第一个被删除的孩子,还是第二个?此时需要用mark来标记

4.P300那句话

因为翻译不好,严重影响理解 一旦第二个孩子也失掉后,x与其父结点之间的联系就被切断了,并成为一个新根。 原文:As soon as the second child has been lost, we cut x from its parent, making it a new root.

三、改进

1.命名

mark的命名不能体现它的作用,影响理解,如果换一个好一点的名字,就不用那么大段的文字去说明 外部函数不需要FIB-HEAP-这样的前缀,因为本来就是为它写的接口 内部函数的名字要说明函数的作用,因为内部函数是被自己调用的,不要给自己添麻烦

2.分解函数

提取了一些对双链表的常用操作

3.合并函数

CUT和CASCADING-CUT合并成一个函数,因为它们其实是一个功能,就是根据策略把孩子结点升为根结点

4.参数和返回值

CUT和CASCADING-CUT中的x和y是父子关系,而且重点是子,父是只为了方便处理,不需要作为参数传进来,在函数里面重新获取一个就可以了。多传一个函数,就一个出错源 对于带参数的函数,增加一返回值。用于告知调用者是否成功,或什么原因导致失败

5.功能

FIB-HEAP-DECREASE-KEY和FIB-HEAP-DELETE这两个函数作用不大。 因为它们的入参是node*。要想调用这两个函数,就必须先获取目标结点的指针。 可是没有一个接口返回指向结点的指针,怎么找到我的目标结点的指针呢? 调用者必须自己在创建结点后保持这个结点,这样不合理

四、代码

1.FibHeap.h 2.FibHeap.cpp 3.测试用例

Previous15-3 编辑距离Next练习题

Last updated 4 years ago

算法导论 第20章 斐波那契堆