{{Heap Running Times}} provides time complexity information for operations across different types of heaps.
{{Heap Running Times |mode = min}}
where
Here are time complexities [1] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
Operation | find-min | delete-min | insert | decrease-key | meld |
---|---|---|---|---|---|
Binary [1] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
Binomial [1] [2] | Θ(1) | Θ(log n) | Θ(1) [a] | Θ(log n) | O(log n) |
Skew binomial [3] | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n) [b] |
Pairing [4] | Θ(1) | O(log n) [a] | Θ(1) | o(log n) [a] [c] | Θ(1) |
Rank-pairing [7] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Fibonacci [1] [8] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Strict Fibonacci [9] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
Brodal [10] [d] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
2–3 heap [12] | Θ(1) | O(log n) [a] | Θ(1) [a] | Θ(1) | O(log n) |
{{Heap Running Times}} provides time complexity information for operations across different types of heaps.
{{Heap Running Times |mode = min}}
where
Here are time complexities [1] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
Operation | find-min | delete-min | insert | decrease-key | meld |
---|---|---|---|---|---|
Binary [1] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
Binomial [1] [2] | Θ(1) | Θ(log n) | Θ(1) [a] | Θ(log n) | O(log n) |
Skew binomial [3] | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n) [b] |
Pairing [4] | Θ(1) | O(log n) [a] | Θ(1) | o(log n) [a] [c] | Θ(1) |
Rank-pairing [7] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Fibonacci [1] [8] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Strict Fibonacci [9] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
Brodal [10] [d] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
2–3 heap [12] | Θ(1) | O(log n) [a] | Θ(1) [a] | Θ(1) | O(log n) |