Minimum element in a max heap

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

Leave a Reply

Your email address will not be published. Required fields are marked *