Posted on by Kalkicode
Code Heap

# Check if a given array is form of max heap

The problem are determining whether a given array can be considered as a valid representation of a max heap. A max heap is a binary tree data structure where each parent node has a value greater than or equal to its child nodes. This ensures that the largest element is at the root of the heap. Your task is to check if a given array follows the properties of a max heap.

## Problem Statement

Given an array of integers, you need to determine whether the array represents a valid max heap or not.

## Example

Let's consider the given array: `[15, 12, 10, 9, 2, 5, 7, 6, 3]`

The array can be visualized as a binary tree:

``````
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6   3
``````

In this case, the array represents a max heap because each parent node's value is greater than or equal to its child nodes' values.

## Idea to Solve

To determine whether the given array represents a max heap, you need to traverse the array and check whether the max heap property is satisfied for each parent node. For a parent node at index `i`, its left child will be at index `2*i + 1` and its right child will be at index `2*i + 2`.

## Pseudocode

``````function heap(arr, size, root):
left = 2 * root + 1
right = 2 * root + 2

if left < size and (arr[left] > arr[root] or right < size and arr[right] > arr[root]):
return false
return true

function is_max_heap(arr, size):
status = true

for i from (size / 2) - 1 to 0:
status = heap(arr, size, i)

return status

main:
arr = [15, 12, 10, 9, 2, 5, 7, 6, 3]
size = length of arr

print arr

if is_max_heap(arr, size):
print "Yes"
else:
print "No"``````

## Algorithm Explanation

1. The `heap` function takes an array, its size, and the index of the root node as arguments. It compares the values of the root node with its left and right children. If the max heap property is violated, it returns false.

2. The `is_max_heap` function iterates through the array, starting from the parent of the last leaf node up to the root. It calls the `heap` function for each parent node to check the max heap property. If any violation is found, it returns false.

3. In the `main` function, the given array is printed, and the `is_max_heap` function is called to determine if the array represents a max heap or not.

## Code Solution

``````//C Program
//Check whether array is form of max heap

#include <stdio.h>

int heap(int arr[],int size,int root)
{
//Get the location of left and right child
int left  = 2*root+1;
int right = 2*root+2;

if(left < size &&  arr[left] > arr[root] ||
(right < size && arr[right] > arr[root]))
{
//Maximum heap properties are not satisfied
return 0;
}
return 1;

}
//Display array elements
void print_data(int arr[],int size)
{

for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
printf("\n");
}
//Check if a given array is form of max heap or not
int is_max_heap(int arr[],int size)
{
int status = 1;

for (int i = (size/2)-1 ; i >= 0 && status==1; i--)
{
status = heap(arr,size,i);

}
return status;

}
int main()
{

//Define collection of array elements
int arr[] = {15, 12, 10,  9,  2,  5,  7,  6, 3};

//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);

//Display array elements
print_data(arr,size);

/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties
if(is_max_heap(arr,size)==1)
{
printf(" Yes\n");
}
else
{
printf(" No\n");
}

return 0;
}```
```

#### Output

`````` 15 12 10  9  2  5  7  6  3
Yes``````
``````#include<iostream>

using namespace std;

/*
C++ Program
Check whether array is form of max heap
*/
class MyHeap {
public:
bool heap(int arr[], int size, int root) {
//Get the location of left and right child
int left = 2 *root + 1;
int right = 2 *root + 2;
if (left < size && arr[left] > arr[root] ||
(right < size && arr[right] > arr[root])) {
return
//Maximum heap properties are not satisfied
false;
}
return true;
}
//Display array elements
void print_data(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
cout << "\n";
}
//Check if a given array is form of max heap or not
bool is_max_heap(int arr[], int size) {
bool status = true;
for (int i = (size / 2) - 1; i >= 0 && status == true; i--) {
status = this->heap(arr, size, i);
}
return status;
}
};
int main() {
MyHeap obj = MyHeap();
int arr[] = {
15,
12,
10,
9,
2,
5,
7,
6,
3
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
//Display array elements
obj.print_data(arr, size);
/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties

if (obj.is_max_heap(arr, size) == true) {
cout << " Yes\n";
} else {
cout << " No\n";
}
return 0;
}```
```

#### Output

`````` 15 12 10 9 2 5 7 6 3
Yes``````
``````/*
Java Program
Check whether array is form of max heap
*/
public class MyHeap {

public boolean heap(int []arr,int size,int root)
{
//Get the location of left and right child
int left  = 2*root+1;
int right = 2*root+2;

if(left < size &&  arr[left] > arr[root] ||
(right < size && arr[right] > arr[root]))
{
//Maximum heap properties are not satisfied
return false;
}
return true;

}
//Display array elements
public void print_data(int []arr,int size)
{

for(int i = 0; i < size; i++)
{
System.out.print("  "+arr[i] );
}
System.out.print("\n");
}
//Check if a given array is form of max heap or not
public boolean is_max_heap(int []arr,int size)
{
boolean status = true;

for (int i = (size/2)-1 ; i >= 0 && status==true; i--)
{
status = heap(arr,size,i);

}
return status;

}
public static void main(String[] args) {

MyHeap obj = new MyHeap();

//Define Collection of array elements
int []arr = {15, 12, 10,  9,  2,  5,  7,  6, 3};

//Get the size of array
int size = arr.length;

//Display array elements
obj.print_data(arr,size);

/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties
if(obj.is_max_heap(arr,size)==true)
{
System.out.print("  Yes\n");
}
else
{
System.out.print("  No\n");
}
}
}```
```

#### Output

`````` 15 12 10 9 2 5 7 6 3
Yes``````
``````/*
C# Program
Check whether array is form of max heap
*/
using System;

public class MyHeap {
public Boolean heap(int[] arr, int size, int root) {
//Get the location of left and right child
int left = 2 * root + 1;
int right = 2 * root + 2;
if (left < size && arr[left] > arr[root] ||
(right < size && arr[right] > arr[root])) {
return false;
}
return true;
}
//Display array elements
public void print_data(int[] arr, int size) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Check if a given array is form of max heap or not
public Boolean is_max_heap(int[] arr, int size) {
Boolean status = true;
for (int i = (size / 2) - 1; i >= 0 && status == true; i--) {
status = heap(arr, size, i);
}
return status;
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
int[]
//Define Collection of array elements
arr = {
15,
12,
10,
9,
2,
5,
7,
6,
3
};
//Get the size of array
int size = arr.Length;
obj.print_data(arr, size);
/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties

if (obj.is_max_heap(arr, size) == true) {
Console.Write(" Yes\n");
} else {
Console.Write(" No\n");
}
}
}```
```

#### Output

`````` 15 12 10 9 2 5 7 6 3
Yes``````
``````<?php
/*
Php Program
Check whether array is form of max heap
*/
class MyHeap {
public 	function heap(\$arr, \$size, \$root) {
//Get the location of left and right child
\$left = 2 *\$root + 1;
\$right = 2 *\$root + 2;
if (\$left < \$size && \$arr[\$left] > \$arr[\$root] ||
(\$right < \$size && \$arr[\$right] > \$arr[\$root])) {
return false;
}
return true;
}
//Display array elements

public 	function print_data(\$arr, \$size) {
for (\$i = 0; \$i < \$size; \$i++) {
echo(" ". \$arr[\$i]);
}
echo("\n");
}
//Check if a given array is form of max heap or not

public 	function is_max_heap(\$arr, \$size) {
\$status = true;
for (\$i = (intval(\$size / 2)) - 1; \$i >= 0 && \$status == true; \$i--) {
\$status = \$this->heap(\$arr, \$size, \$i);
}
return \$status;
}
}

function main() {
\$obj = new MyHeap();
//Define Collection of array elements
\$arr = array(15, 12, 10, 9, 2, 5, 7, 6, 3);
//Get the size of array
\$size = count(\$arr);
//Display array elements

\$obj->print_data(\$arr, \$size);
/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties

if (
\$obj->is_max_heap(\$arr, \$size) == true) {
echo(" Yes\n");
} else {
echo(" No\n");
}

}
main();```
```

#### Output

`````` 15 12 10 9 2 5 7 6 3
Yes``````
``````/*
Node Js Program
Check whether array is form of max heap
*/
class MyHeap {
heap(arr, size, root) {
//Get the location of left and right child
var left = 2 *root + 1;
var right = 2 *root + 2;
if (left < size && arr[left] > arr[root] ||
(right < size && arr[right] > arr[root])) {
return false;
}

return true;
}

//Display array elements
print_data(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}

process.stdout.write("\n");
}

//Check if a given array is form of max heap or not
is_max_heap(arr, size) {
var status = true;
for (var i = (parseInt(size / 2)) - 1; i >= 0 && status == true; i--) {
status = this.heap(arr, size, i);
}

return status;
}
}

function main(args) {
var obj = new MyHeap();
//Define Collection of array elements
var arr = [15, 12, 10, 9, 2, 5, 7, 6, 3];
//Get the size of array
var size = arr.length;
//Display array elements
obj.print_data(arr, size);
/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties

if (obj.is_max_heap(arr, size) == true) {
process.stdout.write(" Yes\n");
} else {
process.stdout.write(" No\n");
}
}

main();```
```

#### Output

`````` 15 12 10 9 2 5 7 6 3
Yes``````
``````# Python 3 Program
# Check whether array is form of max heap
class MyHeap :
def heap(self, arr, size, root) :
# Get the location of left and right child
left = 2 * root + 1
right = 2 * root + 2
if (left < size and arr[left] > arr[root] or(right < size and arr[right] > arr[root])) :
return False

return True

# Display array elements
def print_data(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

# Check if a given array is form of max heap or not
def is_max_heap(self, arr, size) :
status = True
i = (int(size / 2)) - 1
while (i >= 0 and status == True) :
status = self.heap(arr, size, i)
i -= 1

return status

def main() :
obj = MyHeap()
# Define Collection of array elements
arr = [15, 12, 10, 9, 2, 5, 7, 6, 3]
# Get the size of array
size = len(arr)
# Display array elements
obj.print_data(arr, size)

#              15
#            /    \
#           12     10
#          / \     / \
#         9   2   5   7
#        / \
#       6  3
#
# Check max heap properties

if (obj.is_max_heap(arr, size) == True) :
print(" Yes\n", end = "")
else :
print(" No\n", end = "")

if __name__ == "__main__":
main()```
```

#### Output

``````  15  12  10  9  2  5  7  6  3
Yes``````
``````#   Ruby Program
#   Check whether array is form of max heap
class MyHeap
def heap(arr, size, root)
# Get the location of left and right child
left = 2 * root + 1
right = 2 * root + 2
if (left < size && arr[left] > arr[root] ||
(right < size && arr[right] > arr[root]))
return false
end
return true
end
# Display array elements
def print_data(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Check if a given array is form of max heap or not
def is_max_heap(arr, size)
status = true
i = (size / 2) - 1
while (i >= 0 && status == true)
status = self.heap(arr, size, i)
i -= 1
end
return status
end
end
def main()
obj = MyHeap.new()
# Define Collection of array elements
arr = [15, 12, 10, 9, 2, 5, 7, 6, 3]
# Get the size of array
size = arr.length
# Display array elements
obj.print_data(arr, size)

#              15
#            /    \
#           12     10
#          / \     / \
#         9   2   5   7
#        / \
#       6  3
#
# Check max heap properties

if (obj.is_max_heap(arr, size) == true)
print(" Yes\n")
else
print(" No\n")
end
end
main()```
```

#### Output

`````` 15 12 10 9 2 5 7 6 3
Yes
``````
``````/*
Scala Program
Check whether array is form of max heap
*/
class MyHeap {
def heap(arr: Array[Int], size: Int, root: Int): Boolean = {
//Get the location of left and right child
val left: Int = 2 * root + 1;
val right: Int = 2 * root + 2;

if (left < size && arr(left) > arr(root) ||
(right < size && arr(right) > arr(root))) {
return false;
}
return true;
}
//Display array elements
def print_data(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Check if a given array is form of max heap or not
def is_max_heap(arr: Array[Int], size: Int): Boolean = {
var status: Boolean = true;
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0 && status == true) {
status = this.heap(arr, size, i);
i -= 1;
}
return status;
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();

//Define Collection of array elements
val arr: Array[Int] = Array(15, 12, 10, 9, 2, 5, 7, 6, 3);

//Get the size of array
val size: Int = arr.length;

//Display array elements
obj.print_data(arr, size);

/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties

if (obj.is_max_heap(arr, size) == true) {
print(" Yes\n");
} else {
print(" No\n");
}
}
}```
```

#### Output

`````` 15 12 10 9 2 5 7 6 3
Yes``````
``````/*
Swift Program
Check whether array is form of max heap
*/
class MyHeap {
func heap(_ arr: [Int], _ size: Int, _ root: Int) -> Bool {
//Get the location of left and right child
let left: Int = 2 * root + 1;
let right: Int = 2 * root + 2;
if (left < size && arr[left] > arr[root] ||
(right < size && arr[right] > arr[root])) {
return false;
}
return true;
}
//Display array elements
func print_data(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Check if a given array is form of max heap or not
func is_max_heap(_ arr: [Int], _ size: Int) -> Bool {
var status: Bool = true;
var i: Int = (size / 2) - 1;
while (i >= 0 && status == true) {
status = self.heap(arr, size, i);
i -= 1;
}
return status;
}
}
func main() {
let obj: MyHeap = MyHeap();
//Define Collection of array elements
let arr: [Int] = [15, 12, 10, 9, 2, 5, 7, 6, 3];
//Get the size of array
let size: Int = arr.count;
//Display array elements
obj.print_data(arr, size);
/*
15
/    \
12     10
/ \     / \
9   2   5   7
/ \
6  3
*/
//Check max heap properties

if (obj.is_max_heap(arr, size) == true) {
print("  Yes");
} else {
print("  No");
}
}
main();```
```

#### Output

``````  15  12  10  9  2  5  7  6  3
Yes``````

## Time Complexity

The time complexity of this algorithm depends on the size of the array, `n`. The `is_max_heap` function iterates through at most `n/2` parent nodes, and for each parent node, the `heap` function performs constant-time operations. Hence, the overall time complexity is O(n).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post