Uses of Heaps
Priority Queues: heaps ordered by priority. Highest priority
at the top.
Heap Sort:
- insert each element into a heap.
- remove them in ascending order.
Complexity: N insert + N delete. insert and delete are O(logN).
Therefore, Heap Sort is O(NlogN).
Representing a Tree in an Array
Fix maximum height of tree to H, and use an array of size
2**H - 1.
Biggest binary tree of depth 3:
