a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property either:
- max heap - the value of every parent node is greater than its children
- min heap - the value of every parent node is lesser than its children
Heap Implementations & Their Operation Time-Complexities
|
Heap Implementation |
find-min |
delete-min |
insert |
decrease-key |
meld |
|---|---|---|---|---|---|
|
Θ(1) |
Θ(log n) |
O(log n) |
O(log n) |
Θ(n) | |
|
Θ(1) |
Θ(log n) |
Θ(log n) |
O(log n) |
Θ(log n) | |
|
Θ(1) |
Θ(log n) |
Θ(1) |
Θ(log n) |
O(log n) | |
|
Θ(1) |
O(log n) |
Θ(1) |
Θ(1) |
Θ(1) | |
|
Θ(1) |
O(log n) |
Θ(1) |
o(log n) |
Θ(1) | |
|
Θ(1) |
O(log n) |
Θ(1) |
Θ(1) |
Θ(1) | |
|
Θ(1) |
O(log n) |
Θ(1) |
Θ(1) |
Θ(1) | |
|
Θ(1) |
O(log n) |
Θ(1) |
Θ(1) |
Θ(1) | |
|
O(log n) |
O(log n) |
O(log n) |
Θ(1) |
? |