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.pdfIntroduction to Algorithms
- 저자
- Cormen, Thomas H./ Leiserson, Charles E./ Rivest, 지음
- 출판사
- McGraw-Hill | 2001-07-01 출간
- 카테고리
- 과학/기술
- 책소개
- -
