Four concepts that make a heap:
- Structure arrangement(can be ascending or descending)
- Complete BT
- h = log n
- Balanced BT
Can be implemented with array.
Compared to BT, greater values don't have to be on the left side.
Types:
- Max heap(maximum value at top, all children are lesser)
- Min heap(minimum value at top, all children are greater)
Not recommended for search operations.
| Search | Insertion | Deletion |
|---|---|---|
| O(n) | Best case O(n), worst case O(log n) | O(log n) |