Template:Heap Running Times
Jump to navigation
Jump to search
File:Test Template Info-Icon - Version (2).svg Template documentation[view] [edit] [history] [purge]
.svg){kind=link}
Objective
[edit source]{{Heap Running Times}} provides time complexity information for operations across different types of heaps.
Usage
[edit source]{{Heap Running Times |mode = min}}
where
- mode
- optional parameter. If present and set to "max", present information for max heap; otherwise present for min heap
Examples
[edit source]Here are time complexities[1] of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.
| Operation | find-min | delete-min | decrease-key | insert | meld | make-heap[a] |
|---|---|---|---|---|---|---|
| Binary[1] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) | Θ(n) |
| Skew[2] | Θ(1) | O(log n) am. | O(log n) am. | O(log n) am. | O(log n) am. | Θ(n) am. |
| Leftist[3] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) |
| Binomial[1][5] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) am. | Θ(log n)[b] | Θ(n) |
| Skew binomial[6] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) | Θ(log n)[b] | Θ(n) |
| 2–3 heap[8] | Θ(1) | O(log n) am. | Θ(1) | Θ(1) am. | O(log n)[b] | Θ(n) |
| Bottom-up skew[2] | Θ(1) | O(log n) am. | O(log n) am. | Θ(1) am. | Θ(1) am. | Θ(n) am. |
| Pairing[9] | Θ(1) | O(log n) am. | o(log n) am.[c] | Θ(1) | Θ(1) | Θ(n) |
| Rank-pairing[12] | Θ(1) | O(log n) am. | Θ(1) am. | Θ(1) | Θ(1) | Θ(n) |
| Fibonacci[1][13] | Θ(1) | O(log n) am. | Θ(1) am. | Θ(1) | Θ(1) | Θ(n) |
| Strict Fibonacci[14][d] | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n) |
| Brodal[15][d] | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n)[16] |
- ^ make-heap is the operation of building a heap from a sequence of n unsorted elements. It can be done in Θ(n) time whenever meld runs in O(log n) time (where both complexities can be amortized).[2][3] Another algorithm achieves Θ(n) for binary heaps.[4]
- ^ a b c For persistent heaps (not supporting decrease-key), a generic transformation reduces the cost of meld to that of insert, while the new cost of delete-min is the sum of the old costs of delete-min and meld.[7] Here, it makes meld run in Θ(1) time (amortized, if the cost of insert is) while delete-min still runs in O(log n). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.[6]
- ^ Lower bound of [10] upper bound of [11]
- ^ a b Brodal queues and strict Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a persistent data structure achieving the same optimum, except that decrease-key is not supported.
- ^ a b c d Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b c Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).