Implementation

Heapify

Starting with an empty heap, let’s see how to build a heap of N elements.

What happens when a new element is added at the end of a min-heap? Obviously, this new element can violate the heap property. An important point to note is that it violates the heap property for its parent only.

Now we can check this (parent > child) and swap the nodes, after which, the parent might be violating the min-heap property with its parent. We keep checking until we reach the root.