A Min Heap Binary Tree is a Binary Tree where the root node has the minimum key in the tree.

The above definition holds true for all sub-trees in the tree. This is called the Min Heap property.

Almost every node other than the last two layers must have two children. That is, this is almost a complete binary tree, with the exception of the last 2 layers.

The below tree is an example of a min heap binary tree since the above two properties hold.

min_heap_btree.png.webp

Min Heap Btree

Now that we’ve covered what a min heap tree is, let’s look at how we can represent it.


Representation of a Min Heap Tree

A Min Heap Binary Tree is commonly represented as an array, which is indexed according to the below format:

Current Node arr[i]
Parent Node arr[(i-1)/2]
Left Child arr[(2*i) + 1]
Right Child arr[(2*i )+ 2]

The root of the whole tree is at arr[0].

We will use the indexing as shown in the below figure. It’s not very hard to find the pattern here, which will match with the above table.

Min Heap Binary Tree Index

This indexing follows a Level Order Traversal of the Binary Tree, so a Binary Heap array is a Binary Tree using a level order traversal.

Min Heap Array

The above figure shows the array representation of the Min Heap Tree.

Now that we’ve covered the concepts, let’s move onto implementing this in C!


Implementing a Min Heap Tree

We will use the array representation to build the tree. Let’s start writing the structure for the Min Heap.

We’ll have an array of elements, and a size, which gets updated as elements are being inserted or deleted.

The array also has a capacity, which indicates the maximum size of the array.

There are a few functions that we need to write to indicate that we are representing a Min Heap Tree, like finding the parent, and the children.

We’ll write functions to initialize and free the heap.

With that covered, let’s now move on to how we can insert elements!

Inserting onto the Min Heap

The insertion algorithm is simple. This inserts an element into the tree.

Breaking down the algorithm:

  • First, always insert at the bottom of the tree. The initial position of the inserted element is at the last level.
  • We will now need to update the position of this element so that the min-heap property is satisfied.
  • Since the root node of every sub-tree must be the minimum, check the sub-tree of its immediate parent.
  • If the parent is greater than this inserted element, we need to update its position by swapping it.
  • But we are not yet done, since the min-heap property may be violated of the updated node’s sub-tree!
  • We need to keep swapping until we reach the root node, after which we are done.

To understand this procedure, let’s take an example.

Consider the tree below, having only one element.

Min Heap One Element

Let’s insert the element 40. Since there is only one element, it inserts to the bottom, and we observe that the min-heap property is satisfies, since 10 < 40. So there is no need to swap.

min_heap_two_elements.png.webp

Min Heap Two Elements

Next, we’ll insert 50. A similar procedure follows.

Min Heap Three Elements

Next, we’ll insert 5. So now, we first insert to the bottom of the tree, at index 3.

Min Heap State

The min heap property is violated for the sub-tree 1-3, and therefore, for the whole tree. So, we must keep swapping with the parent until we reach the root.

So, we need one more swap, since again, the min-heap property is violated for the sub-tree rooted at node 0.

Alright. Now that we have visualized it, let’s write it down!

We’ll now implement the deletion method.

Delete from the Min Heap

Before we look at deleting an element any index, since the min-heap is very closely associated with the root, we will look at deleting the root first.

To delete the minimum element (i.e the root), we will do the following:

  • Update the root as the last element of the array (tree)
  • We will now remove the last element at the bottom. This is similar to swapping and deleting at the end! Only because we don’t care about the root value anymore, we simply update it instead.
  • The problem again is that we need to maintain the min-heap property.
  • So we must ensure that the whole tree maintains this property. We will use a function called heapify() to do this for us.

So, we know that the deletion method will be complete after we do the heapify() method as well.

The heapify() procedure

This function takes in an element index index, and maintains the min heap property, by swapping with the smallest element of its immediate sub-tree.

The resulting tree will satisfy the min-heap property.

This involves finding the minimum element of the sub-tree and performing a swap with the current element.

After this, we still need to make sure the entire tree satisfies this. So, we need to recursively call the procedure on the smallest element, until we reach the root!

We can now extend this delete_minimum() function, to delete any element.

Deleting an Arbitrary Element

This involves only setting the desired element to the minimum possible value, that will be get_min() - 1, since it must be lesser than the current minimum.

We will now keep swapping until we update the position so that the new root is this element.

Now, we’re back at our old delete_minimum() function! We can simply delete the new root!

With this, our entire deletion procedure will look like this:

Phew! We’re finally done. I’ll now show you the entire code until now, along with the print() function, to visualize the tree.


The Complete Code

Output


Time Complexity of Implementation

The time complexities of the above procedures are mentioned below:

Function Time Complexity
get_min() O(1)
insert_minheap() O(logN)
delete_minimum() Same as insert – O(logN)
heapify() O(logN)
delete_element() O(logN)

Download the Code

You can download the complete code as a Github Gist that I have uploaded. If you have any queries regarding this, do ask them in the comment section below!


Conclusion

In this article, we learned how we can represent a Min Heap Binary Tree, and also look at an implementation in C.

References


By admin

Leave a Reply

%d bloggers like this: