Given a list and index(k), remove the element at that index(k) when in min heap

In this article I will show you how to remove an element at index k from a Min Heap also known as a Minimum Heap. You will learn what a heap data structure is, and the algorithm to delete an element at index k from a Min Heap.

A heap data structure is a special tree that satisfies the heap property, this just means that the parent is less than or equal to the child node for a minimum heap (min heap) and the parent is greater than or equal to the child node for a maximum heap (max heap).

ALGORITHM:

1, Delete a node from the array 
       (this creates a "hole" and the tree is no longer "complete")

    2. Replace the deletion node
       with the "farthest right node" on the lowest level
       of the Binary Tree
       (This step makes the tree into a "complete binary tree")

    3. Heapify (fix the heap):

         if ( value in replacement node < its parent node )
            Filter the replacement node UP the binary tree
         else
	    Filter the replacement node DOWN the binary tree

Min heap of size n

Now we will visualize the heap structure before and after the deletion of node

Here K=2(Index from which element has to be deleted)

Before deletion

After deletion

Implementation:

Now the heap property holds true and we are done !