- Heap Property: Parent is always greater than child
- child for parent i are 2i+1 & 2i+2 (zero based starting index).
- height of tree is log(n) where n is number of elements.
- heap: is a B-Tree with heap property.
Inserting element to a Heap: Add the element to the last available position and keep swapping with parent till you find its position.
Heapify a tree A at inex i means make the tree at index i into heap:
Compare A[i] with large of the 2 children and swap if necessary. this MAY break the heap property of the child, so repeat the process with the swap child. O(logn)
Building a Heap: start at n/2 and down to 1 run Heapify at every node. Runs in linear time.
Heap Sort: exchange the last element with max element and decrease the length of the array and repeat the whole process.