Last Updated on June 27, 2022 by Ria Pathak
Problem statement:
The Statement is quite straightforward given a max heap, find the minimum element present in the heap.
A Max heap is a complete binary tree and in the max heap, the value at the root node is greater than its children.
Dry Run
Brute force Approach:
You can check all the nodes present in the tree and pick out the minimum element from the tree, but in this solution, we do not use the property of max heap, and the time and space complexity are O(N).
We’ll use an array to store them. After that, we can traverse the array and find the minimum element present in the array.
#include <bits/stdc++.h>
using namespace std;
int findMinimumElement(int heap[], int n)
{
int minimumElement = heap[0];
for (int i = 1; i < n; ++i)
minimumElement = min(minimumElement, heap[i]);
return minimumElement;
}
int main()
{
int n = 10;
int heap[] = { 200, 180, 100, 12, 9, 9, 3, 5, 6, 8 };
cout << findMinimumElement(heap, n);
return 0;
}
public class Improve {
static int findMinimumElement(int heap[], int n)
{
int minimumElement = heap[0];
for (int i = 1; i < n; ++i)
minimumElement
= Math.min(minimumElement, heap[i]);
return minimumElement;
}
public static void main(String args[])
{
int n = 10;
int heap[] = { 20, 18, 10, 12, 9, 9, 3, 5, 6, 8 };
System.out.println(findMinimumElement(heap, n));
}
}
def findMiniumumElement(heap, n):
minimumElement = heap[0]
for i in range(1, n):
minimumElement = min(minimumElement, heap[i])
return minimumElement
n = 10 # Numbers Of Node
heap = [20, 18, 10, 12, 8,
9, 3, 5, 6, 8]
print(findMiniumumElement(heap, n))
Efficient Approach:
As we know the property of max heap i.e. the value of the parent must be greater than its children due to which we can easily conclude that parent nodes are not the minimum element so we can search for the minimum element in the leaf nodes.
If the heap contains n nodes then there will be ceil(n/2) leaf nodes.
#include <bits/stdc++.h>
using namespace std;
int findMinimumElement(int heap[], int n)
{
int minimumElement = heap[n / 2];
for (int i = 1 + n / 2; i < n; ++i)
minimumElement = min(minimumElement, heap[i]);
return minimumElement;
}
int main()
{
// Number of nodes
int n = 10;
int heap[] = { 200, 180, 100, 12, 9, 9, 3, 5, 6, 8 };
cout << findMinimumElement(heap, n);
return 0;
}
import java.util.*;
import java.lang.*;
class prepbytes {
static int findMinimumElement(int heap[], int n)
{
int minimumElement = heap[n / 2];
for (int i = 1 + n / 2; i < n; ++i)
minimumElement
= Math.min(minimumElement, heap[i]);
return minimumElement;
}
public static void main(String args[])
{
// Number of nodes
int n = 10;
int heap[] = new int[] { 20, 18, 10, 12, 9,
9, 3, 5, 6, 8 };
System.out.println(findMinimumElement(heap, n));
}
}
def findMiniumumElement(heap, n):
minimumElement = heap[n // 2]
for i in range(1 + n // 2, n):
minimumElement = min(minimumElement,
heap[i])
return minimumElement
n = 10 # Numbers Of Node
heap = [20, 18, 10, 12, 9,
9, 3, 5, 6, 8]
print(findMiniumumElement(heap, n))
Complexity
Time and space complexity remains O(N) as a constant factor of 1/2 does not affect any asymptotic complexity.
This article tried to discuss How to find Minimum element in a max heap. Hope this blog helps you understand the implementation. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes