Heap

A Heap is a binary tree. It has two forms: min. Heap and max. Heap.

In a min. Heap, the root of any sub-tree is smaller than its children. The deeper we go into the children, the bigger they are. The minimum element is the root of the heap.

In a max. Heap, the root of any-sub tree is bigger than its children. The deeper we go into the children, the smaller they are. The maximum element is the root of the heap.

A heap can be implemented in a array using a simple mapping:

• get parent: (index - 2) / 2
• left: index x 2 + 1
• right: index x 2 + 2

Insertion

Insert the new element at the leaves and bubble it up. Or, we can replace the min. element with the new element and bubble it down.

Resources

https://www.youtube.com/watch?v=oSWTXtMglKE