知识卡片

普通读书笔记卡 · 3635

斐波那契堆降低减键摊还费

理解等级:中级

斐波那契堆是可合并堆:

  • INSERT(插入)、MINIMUM(查看最小键)和 UNION(合并两堆)的实际与摊还时间均为 O(1);
  • EXTRACT-MIN(取出并删除最小键)和 DELETE(删除指定节点)为 O(lg n) 摊还时间;
  • DECREASE-KEY(减小指定节点的键)为 O(1) 摊还时间。

这里 n 是当前堆中的节点数。

频繁减键的图算法可利用后一性质;严格斐波那契堆把这些界变为实际时间。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第五部分 高级数据结构 · 查看原书依据

      Fibonacci heaps [156] implement mergeable heaps (see Problem 10-2 on page 268) with the operations INSERT, MINIMUM, and UNION taking only O(1) actual and amortized time, and the operations EXTRACT-MIN and DELETE taking O(lg n) amortized time. The most significant advantage of these data structures, however, is that DECREASE-KEY takes only O(1) amortized time. Strict Fibonacci heaps [73], developed later, made all of these time bounds actual.

    参考来源

    - 位置:《算法导论(第4版)》第五部分引言《高级数据结构》(OEBPS/part005.xhtml,文本字符[0,5000))。 - 结论依据:原文逐项列出普通斐波那契堆的实际或摊还界,并说明严格变种把所有列出的界变为实际时间。 - 原始内容:Fibonacci heaps [ 156 ] implement mergeable heaps (see Problem 10-2 on page 268) with the operations I NSERT , M INIMUM , and U NION taking only O (1) actual and amortized time, and the operations E XTRACT -M IN and D ELETE taking O (lg n ) amortized time. The most significant advantage of these data structures, however, is that D ECREASE -K EY takes only O (1) amortized time. Strict Fibonacci heaps [ 73 ], developed later, made all of these time bounds actual.