Check if a given array is form of min heap

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

Problem Statement

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

Example

Let's consider the given array: [1, 5, 6, 9, 7, 10, 10, 14]

The array can be visualized as a binary tree:

           1
         /   \ 
        5     6
       / \   / \
      6   9 7   10
     / \
    10  14

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

Idea to Solve

To determine whether the given array represents a min heap, you need to traverse the array and check whether the min 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_min_heap(arr, size):
   status = true
   
   for i from (size / 2) - 1 to 0:
       status = heap(arr, size, i)
   
   return status

main:
   arr = [1, 5, 6, 9, 7, 10, 10, 14]
   size = length of arr
   
   print arr
   
   if is_min_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 min heap property is violated, it returns false.

2. The is_min_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 min heap property. If any violation is found, it returns false.

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

Code Solution

• C
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//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;
}

  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;
}

 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");
    }
  }
}

 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");
		}
	}
}

 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();

 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();

 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()

  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()

 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");
		}
	}
}

 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();

  1  5  6  9  7  10  10  14
  Yes

Time Complexity

The time complexity of this algorithm depends on the size of the array, n. The is_min_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).