Check if a given array is form of min heap
Here given code implementation process.
//C Program
//Check whether array is form of min 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]))
{
//min 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 min heap or not
int is_min_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[] = {1, 5, 6, 9, 7, 10, 10, 14};
//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Display array elements
print_data(arr,size);
//Check min heap properties
if(is_min_heap(arr,size)==1)
{
printf(" Yes\n");
}
else
{
printf(" No\n");
}
return 0;
}
Output
1 5 6 9 7 10 10 14
Yes
/*
C++ Program
Check whether array is form of min heap
*/
#include<iostream>
using namespace std;
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
//min 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 min heap or not
bool is_min_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[] = {
1,
5,
6,
9,
7,
10,
10,
14
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
//Display array elements
obj.print_data(arr, size);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Check min heap properties
if (obj.is_min_heap(arr, size) == true) {
cout << " Yes\n";
} else {
cout << " No\n";
}
return 0;
}
Output
1 5 6 9 7 10 10 14
Yes
/*
Java Program
Check whether array is form of min 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]))
{
//min 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 min heap or not
public boolean is_min_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 = {1, 5, 6, 9, 7, 10, 10, 14};
//Get the size of array
int size = arr.length;
//Display array elements
obj.print_data(arr,size);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Check min heap properties
if(obj.is_min_heap(arr,size)==true)
{
System.out.print(" Yes\n");
}
else
{
System.out.print(" No\n");
}
}
}
Output
1 5 6 9 7 10 10 14
Yes
/*
C# Program
Check whether array is form of min 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 min heap or not
public Boolean is_min_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 = {
1,
5,
6,
9,
7,
10,
10,
14
};
//Get the size of array
int size = arr.Length;
obj.print_data(arr, size);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Check min heap properties
if (obj.is_min_heap(arr, size) == true) {
Console.Write(" Yes\n");
} else {
Console.Write(" No\n");
}
}
}
Output
1 5 6 9 7 10 10 14
Yes
<?php
/*
Php Program
Check whether array is form of min 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 min heap or not
public function is_min_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(1, 5, 6, 9, 7, 10, 10, 14);
//Get the size of array
$size = count($arr);
//Display array elements
$obj->print_data($arr, $size);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Check min heap properties
if (
$obj->is_min_heap($arr, $size) == true) {
echo(" Yes\n");
} else {
echo(" No\n");
}
}
main();
Output
1 5 6 9 7 10 10 14
Yes
/*
Node Js Program
Check whether array is form of min 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 min heap or not
is_min_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 = [1, 5, 6, 9, 7, 10, 10, 14];
//Get the size of array
var size = arr.length;
//Display array elements
obj.print_data(arr, size);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Check min heap properties
if (obj.is_min_heap(arr, size) == true) {
process.stdout.write(" Yes\n");
} else {
process.stdout.write(" No\n");
}
}
main();
Output
1 5 6 9 7 10 10 14
Yes
# Python 3 Program
# Check whether array is form of min heap
class MyHeap :
def heap(self, 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
# 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 min heap or not
def is_min_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()
arr = [1, 5, 6, 9, 7, 10, 10, 14]
size = len(arr)
obj.print_data(arr, size)
# 1
# / \
# 5 6
# / \ / \
# 6 9 7 10
# / \
# 10 14
#
# Check min heap properties
if (obj.is_min_heap(arr, size) == True) :
print(" Yes")
else :
print(" No")
if __name__ == "__main__":
main()
Output
1 5 6 9 7 10 10 14
Yes
# Ruby Program
# Check whether array is form of min heap
class MyHeap
def heap(arr, size, root)
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 min heap or not
def is_min_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()
arr = [1, 5, 6, 9, 7, 10, 10, 14]
size = arr.length
obj.print_data(arr, size)
# 1
# / \
# 5 6
# / \ / \
# 6 9 7 10
# / \
# 10 14
#
# Check min heap properties
if (obj.is_min_heap(arr, size) == true)
print(" Yes\n")
else
print(" No\n")
end
end
main()
Output
1 5 6 9 7 10 10 14
Yes
/*
Scala Program
Check whether array is form of min heap
*/
class MyHeap {
def heap(arr: Array[Int], size: Int, root: Int): Boolean = {
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 min heap or not
def is_min_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();
val arr: Array[Int] = Array(1, 5, 6, 9, 7, 10, 10, 14);
val size: Int = arr.length;
obj.print_data(arr, size);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Check min heap properties
if (obj.is_min_heap(arr, size) == true) {
print(" Yes\n");
} else {
print(" No\n");
}
}
}
Output
1 5 6 9 7 10 10 14
Yes
/*
Swift Program
Check whether array is form of min heap
*/
class MyHeap {
func heap(_ arr: [Int], _ size: Int, _ root: Int) -> Bool {
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 min heap or not
func is_min_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();
let arr: [Int] = [1, 5, 6, 9, 7, 10, 10, 14];
let size: Int = arr.count;
obj.print_data(arr, size);
/*
1
/ \
5 6
/ \ / \
6 9 7 10
/ \
10 14
*/
//Check min heap properties
if (obj.is_min_heap(arr, size) == true) {
print(" Yes");
} else {
print(" No");
}
}
main();
Output
1 5 6 9 7 10 10 14
Yes
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.
New Comment