프로그래밍로그

Fibonacci heaps are especially desirable when the number of EXTRACT-MIN and DELETE operations is small relative to the number of other operations performed. This situation arises in many applications. For example, some algorithms for graph problems may call DECREASE-KEY once per edge. For dense graphs, which have many edges, the O(1) amortized time of each call of DECREASE-KEY adds up to a big improvement over the Θ(lg n) worst-case time of binary or binomial heaps.

From a practical point of view, however, the constant factors and programming complexity of Fibonacci heaps make them less desirable than ordinary binary (or k-ary) heaps for most applications. Thus, Fibonacci heaps are predominantly of theoretical interest.

Binary heap과 Binomial heap에서 각각의 operation이 왜 위와 같은 복잡도가 나오는지 잘 설명해주는 강의노트

binary_and_binomial_heaps.pdf

---

Introduction to Algorithms

저자

Cormen, Thomas H./ Leiserson, Charles E./ Rivest, 지음

출판사

McGraw-Hill | 2001-07-01 출간

카테고리

과학/기술

책소개

-

---