Implementation
Explore heap implementation for competitive programming by understanding heapify operations, building a min-heap efficiently, and extracting the minimum element while maintaining heap properties. This lesson guides you through insertion and removal steps along with key conditions to preserve the heap structure.
We'll cover the following...
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.
Building the heap
We can build a min-heap using an array of ...