When a data structure is required to manage insertion, deletion, and locating the minimum in O(Logn) time complexity, the Min Heap proves to be invaluable. This guide delves into the implementation of Min Heap in C++. A binary tree that conforms to either a Min Heap or a Max Heap is known as a Binary Heap. In a Max Binary Heap, the key at the root must be the largest among all keys in the heap. This key relationship must hold true recursively for every node in the binary tree. Analogous to the Min Heap is the Min Binary Heap.
Algorithm of MIN heap:
For min_heap:
Begin
Declare function min_heap(int *a, int m, int n)
Declare j, t of the integer datatype.
Initialize t = a[m].
j = 2 * m;
while (j <= n) do
if (j < n && a[j+1] < a[j]) then
j = j + 1
if (t < a[j]) then
break
else if (t >= a[j]) then
a[j / 2] = a[j]
j = 2 * j
a[j/2] = t
return
End.
For build_minheap:
Begin
Declare function build_minheap(int *a,int n).
Declare k of the integer datatype.
for(k = n/2; k >= 1; k--)
Call function min_heap(a,k,n)
End.
Example:
Let's consider an example to demonstrate the implementation of a Min Heap in C++:
#include <iostream>
#include <conio.h>
using namespace std;
void min_heapify(int *arr, int n, int i) {
int smallest = i;
int left_child = 2 * i + 1;
int right_child = 2 * i + 2;
if (left_child < n && arr[left_child] < arr[smallest])
smallest = left_child;
if (right_child < n && arr[right_child] < arr[smallest])
smallest = right_child;
if (smallest != i) {
swap(arr[i], arr[smallest]);
min_heapify(arr, n, smallest);
}
}
void build_min_heap(int *arr, int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
min_heapify(arr, n, i);
}
}
int main() {
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;
int arr[100];
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
build_min_heap(arr, n);
cout << "Min Heap:\n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
getch();
return 0;
}
Output:
Enter the number of elements in the array: 10
Enter 10 elements: 25 10 30 5 15 40 20 35 45 50
Min Heap:
5 10 20 25 15 40 30 35 45 50
C++ Representation of Min Heap
MinHeap is stored within an array where the first element is represented by Arr[0].
For a node at index i:
(i-1)/2 is the index of the parent node.
(2*i + 1) is the index of the left child.
(2*i + 2) is the index of the right child.
Important MinHeap Methods:
insert:
At the conclusion of the heap array, a fresh element gets added. Subsequently, the integrity of the heap is restored by replacing the current element with its parent until the parent's value surpasses the current value. Adding a new item to the MinHeap takes O(Logn) time complexity.
getMin:
It returns the value of the root element, which is the smallest element. The getMin function in a MinHeap has a time complexity of O(1).
extractMin:
The main element of MinHeap is removed and retrieved through this process. The final element in the heap array is interchanged with the root element prior to executing the Heapify process on MinHeap. The time complexity of the ExtractMin operation is O(Logn).
decreaseKey:
The key situated at index i decreases in value when applying this method. This strategy demonstrates a time complexity of O(Logn).
delete:
The element at index i is eliminated through this process. The deletion operation in MinHeap has a time complexity of O(Logn).
Features of a Binary Heap
These are Binary Heap's characteristics:
It represents a complete binary tree where all levels are fully filled, except possibly for the last level which is filled from left to right. This property enables the binary heap to be stored efficiently in a one-dimensional array.
There exist two variations of binary heaps: Min Heap and Max Heap. The primary element at the root holds the smallest or largest value within the Min/Max Heap.
Conclusion:
The Min Heap was discussed in this article, focusing on the implementation in C++. Additionally, some essential methods of the Min Heap were explored.
