Heap

A Heap is a complete 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 O(log n)

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.

Extract min. element O(log n)

The min. element of min. Heap is the root. To remove it, swap with the bottom-most right-most element and bubble it down, swapping with the smaller element.

Resources

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