A non-empty binary tree is a min-heap if:
- The key associated with the root is less than or equal to the keys associated with either of the sub-trees (if any).
- Both of the sub-trees (if any) are also binary min-heaps.
Examples of Binary Heap:
- Leftish Heap
- Skew Heap
To maintain the heap as a complete binary tree, we do as follow:
- Delete the top node.
- Put the last node (the node with the biggest index) to the root.
- Percolate the node down with the smallest of its new children.
- Stop when both children are larger than it.
Put the new node as the child of an arbitrary node(e.g. a leaf node), then percolate it.