Binary Heap vs Binomial Heap vs Fibonacci Heap vs Paring Heap vs Brodal Queue

Procedure	Binary Heap (Worst-Case)	Binomial Heap (Worst-Case)	Fibonacci Heap (Amortized)	Pairing Heap (Amortized)	Brodal Queue (Worst-Case)
MAKE-HEAP	Θ(1)	Θ(1)	Θ(1)	?	O(1)
INSERT	Θ(lg n)	O(lg n)	Θ(1)	O(1)	O(1)
MINIMUM	Θ(1)	O(lg n)	Θ(1)	O(1)	O(1)
EXTRACT-MIN	Θ(lg n)	Θ(lg n)	O(lg n)	O(lg n)	O(lg n)
UNION	Θ(n)	Θ(lg n)	Θ(1)	O(1)	O(1)
DECREASE-KEY	Θ(lg n)	Θ(lg n)	Θ(1)	O(lg n)	O(1)
DELETE	Θ(lg n)	Θ(lg n)	O(lg n)	O(lg n)	O(lg n)

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 출간

카테고리

과학/기술

책소개

-

---