2. Intro to Heap #
Created Friday 14 February 2020
BST has the following disadvantages:
- Balancing factor, we have to check if it is balanced, after every insertion/deletion.
- Storing is difficult, i.e nodes->data + nodes*pointers, i.e as Binary Tree. Too much size requirement.
So we make a new data structure - called heap.
A heap must satisify 2 properties at all times:
- **Complete Binary Tree **property - it has 2^h^-1 spaces. Complete - all levels are filled completely, except the last one(although it must be filled from left to right).
- **Heap order **property - all nodes must be greater than their children, in case of a max-heap and smaller than their children for a min-heap.
- Purpose of the CBT property - maintains a nearly balanced tree at height lg(n).
- Purpose of the heap order property - maintains max/min at the root node.