Min Heap is a special type of data structure, which is a complete binary tree that follows the following two properties:
- All nodes in the Min Heap are greater than or equal to their children.
- The root node of the Min Heap is the minimum of all nodes.
Min Heap is a common data structure used in many algorithms such as heapsort, priority queues, and graph algorithms. It is also used to implement efficient priority queues. This article will discuss the tree structure of Min Heap, time complexity of access, search, insertion, and deletion, as well as the space complexity of Min Heap in C++.
Tree Structure of Min Heap
A Min Heap is a complete binary tree, meaning it is a binary tree in which all levels are filled except for the last level and all nodes are as far left as possible. The root node of a Min Heap is the minimum of all nodes, and all nodes in the Min Heap are greater than or equal to their children. In the following example of a Min Heap, the root node is 4, and all of its children (2 and 6) are greater than or equal to it.
int MinHeap[7] = {4, 2, 6, 1, 3, 5, 7};
Time Complexity
The time complexity of access, search, insertion, and deletion in a Min Heap is as follows:
- Access: The time complexity of access in a Min Heap is O(1), as we can directly access the root node which is the minimum.
- Search: The time complexity of search in a Min Heap is O(n), as we need to traverse the tree to find the element we are searching for.
- Insertion: The time complexity of insertion in a Min Heap is O(log n), as we need to insert the new element in the correct position in the heap.
- Deletion: The time complexity of deletion in a Min Heap is O(log n), as we need to delete the element from the heap and rearrange the elements accordingly.
Space Complexity
The space complexity of a Min Heap is O(n), as we need to store all of the nodes in the heap.
C++ Implementation
We can implement a Min Heap in C++ using an array. We can use the following code to create a Min Heap of size 7.
// create an array of size 7
int MinHeap[7];
// insert elements into the array
MinHeap[0] = 4;
MinHeap[1] = 2;
MinHeap[2] = 6;
MinHeap[3] = 1;
MinHeap[4] = 3;
MinHeap[5] = 5;
MinHeap[6] = 7;
// create a function to heapify the array
void heapify(int MinHeap[], int n, int i)
{
int smallest = i; // root
int l = 2*i + 1; // left child
int r = 2*i + 2; // right child
// if left child is smaller than root
if (l < n && MinHeap[l] < MinHeap[smallest])
smallest = l;
// if right child is smaller than root
if (r < n && MinHeap[r] < MinHeap[smallest])
smallest = r;
// if root is not smallest
if (smallest != i)
{
swap(MinHeap[i], MinHeap[smallest]);
// heapify the root
heapify(MinHeap, n, smallest);
}
}
// create a function to build the Min Heap
void buildMinHeap(int MinHeap[], int n)
{
// build the heap from the bottom up
for (int i = n / 2 - 1; i >= 0; i--)
heapify(MinHeap, n, i);
}
Conclusion
In conclusion, Min Heap is a special type of data structure that is used in many algorithms. It is a complete binary tree in which all nodes are greater than or equal to their children, and the root node is the minimum of all nodes. The time complexity of access, search, insertion, and deletion in a Min Heap is O(1), O(n), O(log n), and O(log n) respectively. The space complexity of Min Heap is O(n). Min Heap can be implemented in C++ using an array.
Exercises
Create a function to insert an element into a Min Heap.
// function to insert an element into a Min Heap
void insert(int MinHeap[], int n, int x)
{
// insert the element at the end of the heap
MinHeap[n] = x;
// heapify the root node
int i = n;
while (i != 0 && MinHeap[(i - 1)/2] > MinHeap[i])
{
swap(MinHeap[(i - 1)/2], MinHeap[i]);
i = (i - 1) / 2;
}
}
Create a function to delete an element from a Min Heap.
// function to delete an element from a Min Heap
void deleteElement(int MinHeap[], int n, int x)
{
// find the element to be deleted
int i;
for (i = 0; i < n; i++)
if (MinHeap[i] == x)
break;
// replace the element to be deleted with the last element in the heap
swap(MinHeap[i], MinHeap[n - 1]);
// heapify the root node
i = 0;
while (i < n - 1 && MinHeap[i] > MinHeap[2*i + 1])
{
swap(MinHeap[i], MinHeap[2*i + 1]);
i = 2*i + 1;
}
}
Create a function to sort a Min Heap.
// function to sort a Min Heap
void heapSort(int MinHeap[], int n)
{
// build the heap from the bottom up
for (int i = n / 2 - 1; i >= 0; i--)
heapify(MinHeap, n, i);
// sort the heap
for (int i = n - 1; i >= 0; i--)
{
// move the root node to the end
swap(MinHeap[i], MinHeap[0]);
// heapify the root node
heapify(MinHeap, i, 0);
}
}
Create a function to find the minimum element in a Min Heap.
// function to find the minimum element in a Min Heap
int minElement(int MinHeap[], int n)
{
// the root node is the minimum element
return MinHeap[0];
}
Create a function to search for an element in a Min Heap.
// function to search for an element in a Min Heap
bool searchElement(int MinHeap[], int n, int x)
{
// traverse the heap to search for the element
for (int i = 0; i < n; i++)
{
if (MinHeap[i] == x)
return true;
}
return false;
}