How to Draw a Three Min Heap Tree
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.
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.
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.
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.
typedef struct MinHeap MinHeap; struct MinHeap { int* arr; // Current Size of the Heap int size; // Maximum capacity of the heap int capacity; }; 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.
int parent(int i) { // Get the index of the parent return (i - 1) / 2; } int left_child(int i) { return (2*i + 1); } int right_child(int i) { return (2*i + 2); } int get_min(MinHeap* heap) { // Return the root node element, // since that's the minimum, by the min-heap // property return heap->arr[0]; } We'll write functions to initialize and free the heap.
MinHeap* init_minheap(int capacity) { MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap)); minheap->arr = (int*) calloc (capacity, sizeof(int)); minheap->capacity = capacity; minheap->size = 0; return minheap; } void free_minheap(MinHeap* heap) { if (!heap) return; free(heap->arr); free(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.
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.
Next, we'll insert 50. A similar procedure follows.
Next, we'll insert 5. So now, we first insert to the bottom of the tree, at index 3.
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!
MinHeap* insert_minheap(MinHeap* heap, int element) { // Inserts an element to the min heap // We first add it to the bottom (last level) // of the tree, and keep swapping with it's parent // if it is lesser than it. We keep doing that until // we reach the root node. So, we will have inserted the // element in it's proper position to preserve the min heap property if (heap->size == heap->capacity) { fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element); return heap; } // We can add it. Increase the size and add it to the end heap->size++; heap->arr[heap->size - 1] = element; // Keep swapping until we reach the root int curr = heap->size - 1; // As long as you aren't in the root node, and while the // parent of the last element is greater than it while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) { // Swap int temp = heap->arr[parent(curr)]; heap->arr[parent(curr)] = heap->arr[curr]; heap->arr[curr] = temp; // Update the current index of element curr = parent(curr); } return heap; } 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.
MinHeap* delete_minimum(MinHeap* heap) { // Deletes the minimum element, at the root if (!heap || heap->size == 0) return heap; int size = heap->size; int last_element = heap->arr[size-1]; // Update root value with the last element heap->arr[0] = last_element; // Now remove the last element, by decreasing the size heap->size--; size--; // We need to call heapify(), to maintain the min-heap // property heap = heapify(heap, 0); return heap; } 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!
MinHeap* heapify(MinHeap* heap, int index) { // Rearranges the heap as to maintain // the min-heap property if (heap->size <= 1) return heap; int left = left_child(index); int right = right_child(index); // Variable to get the smallest element of the subtree // of an element an index int smallest = index; // If the left child is smaller than this element, it is // the smallest if (left < heap->size && heap->arr[left] < heap->arr[index]) smallest = left; // Similarly for the right, but we are updating the smallest element // so that it will definitely give the least element of the subtree if (right < heap->size && heap->arr[right] < heap->arr[smallest]) smallest = right; // Now if the current element is not the smallest, // swap with the current element. The min heap property // is now satisfied for this subtree. We now need to // recursively keep doing this until we reach the root node, // the point at which there will be no change! if (smallest != index) { int temp = heap->arr[index]; heap->arr[index] = heap->arr[smallest]; heap->arr[smallest] = temp; heap = heapify(heap, smallest); } return heap; } 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:
MinHeap* delete_element(MinHeap* heap, int index) { // Deletes an element, indexed by index // Ensure that it's lesser than the current root heap->arr[index] = get_min(heap) - 1; // Now keep swapping, until we update the tree int curr = index; while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) { int temp = heap->arr[parent(curr)]; heap->arr[parent(curr)] = heap->arr[curr]; heap->arr[curr] = temp; curr = parent(curr); } // Now simply delete the minimum element heap = delete_minimum(heap); return heap; } 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
#include <stdio.h> #include <stdlib.h> typedef struct MinHeap MinHeap; struct MinHeap { int* arr; // Current Size of the Heap int size; // Maximum capacity of the heap int capacity; }; int parent(int i) { // Get the index of the parent return (i - 1) / 2; } int left_child(int i) { return (2*i + 1); } int right_child(int i) { return (2*i + 2); } int get_min(MinHeap* heap) { // Return the root node element, // since that's the minimum return heap->arr[0]; } MinHeap* init_minheap(int capacity) { MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap)); minheap->arr = (int*) calloc (capacity, sizeof(int)); minheap->capacity = capacity; minheap->size = 0; return minheap; } MinHeap* insert_minheap(MinHeap* heap, int element) { // Inserts an element to the min heap // We first add it to the bottom (last level) // of the tree, and keep swapping with it's parent // if it is lesser than it. We keep doing that until // we reach the root node. So, we will have inserted the // element in it's proper position to preserve the min heap property if (heap->size == heap->capacity) { fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element); return heap; } // We can add it. Increase the size and add it to the end heap->size++; heap->arr[heap->size - 1] = element; // Keep swapping until we reach the root int curr = heap->size - 1; // As long as you aren't in the root node, and while the // parent of the last element is greater than it while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) { // Swap int temp = heap->arr[parent(curr)]; heap->arr[parent(curr)] = heap->arr[curr]; heap->arr[curr] = temp; // Update the current index of element curr = parent(curr); } return heap; } MinHeap* heapify(MinHeap* heap, int index) { // Rearranges the heap as to maintain // the min-heap property if (heap->size <= 1) return heap; int left = left_child(index); int right = right_child(index); // Variable to get the smallest element of the subtree // of an element an index int smallest = index; // If the left child is smaller than this element, it is // the smallest if (left < heap->size && heap->arr[left] < heap->arr[index]) smallest = left; // Similarly for the right, but we are updating the smallest element // so that it will definitely give the least element of the subtree if (right < heap->size && heap->arr[right] < heap->arr[smallest]) smallest = right; // Now if the current element is not the smallest, // swap with the current element. The min heap property // is now satisfied for this subtree. We now need to // recursively keep doing this until we reach the root node, // the point at which there will be no change! if (smallest != index) { int temp = heap->arr[index]; heap->arr[index] = heap->arr[smallest]; heap->arr[smallest] = temp; heap = heapify(heap, smallest); } return heap; } MinHeap* delete_minimum(MinHeap* heap) { // Deletes the minimum element, at the root if (!heap || heap->size == 0) return heap; int size = heap->size; int last_element = heap->arr[size-1]; // Update root value with the last element heap->arr[0] = last_element; // Now remove the last element, by decreasing the size heap->size--; size--; // We need to call heapify(), to maintain the min-heap // property heap = heapify(heap, 0); return heap; } MinHeap* delete_element(MinHeap* heap, int index) { // Deletes an element, indexed by index // Ensure that it's lesser than the current root heap->arr[index] = get_min(heap) - 1; // Now keep swapping, until we update the tree int curr = index; while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) { int temp = heap->arr[parent(curr)]; heap->arr[parent(curr)] = heap->arr[curr]; heap->arr[curr] = temp; curr = parent(curr); } // Now simply delete the minimum element heap = delete_minimum(heap); return heap; } void print_heap(MinHeap* heap) { // Simply print the array. This is an // inorder traversal of the tree printf("Min Heap:\n"); for (int i=0; i<heap->size; i++) { printf("%d -> ", heap->arr[i]); } printf("\n"); } void free_minheap(MinHeap* heap) { if (!heap) return; free(heap->arr); free(heap); } int main() { // Capacity of 10 elements MinHeap* heap = init_minheap(10); insert_minheap(heap, 40); insert_minheap(heap, 50); insert_minheap(heap, 5); print_heap(heap); // Delete the heap->arr[1] (50) delete_element(heap, 1); print_heap(heap); free_minheap(heap); return 0; } Output
Min Heap: 5 -> 50 -> 40 -> Min Heap: 5 -> 40 -> 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
- An illustration of Heaps, from Cormen
- Wikipedia article on Binary Heaps
Source: https://www.journaldev.com/36805/min-heap-binary-tree
0 Response to "How to Draw a Three Min Heap Tree"
Post a Comment