知识卡片
斐波那契堆降低减键摊还费
斐波那契堆是可合并堆:
INSERT(插入)、MINIMUM(查看最小键)和UNION(合并两堆)的实际与摊还时间均为O(1);EXTRACT-MIN(取出并删除最小键)和DELETE(删除指定节点)为O(lg n)摊还时间;DECREASE-KEY(减小指定节点的键)为O(1)摊还时间。
这里 n 是当前堆中的节点数。
频繁减键的图算法可利用后一性质;严格斐波那契堆把这些界变为实际时间。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.