Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Minimum element in a max heap

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.

### 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