Question

Write a C++ program to test if a given array satisfies the constraints of min heap and max heap.

      bool isMinHeap(int arr[],int size);

      bool isMaxHeap(int arr[],int size);

Also write code for this function:-

      int heapPlay(int arr[],int size);

The function returns an integer as follows:-

    1. If the array is a min heap return the minimum element

    2. If the array is a max heap return maximum element

    3. Return 0, if the array is a min heap and a max heap

    4. Return -1, if the array is neither a min heap nor a max heap

Ex.

Input - Contains size on line 1, an array on line 2.

Output - We will test your three methods

Input -

    3

1 2 3

Output -

isMinHeap ->   true

isMaxHeap ->   false

heapPlay ->    1

Sample Input 1:

1
5

Sample Output 1:

1 1 0

Sample Input 2:

3
9 8 7

Sample Output 2:

0 1 9

template:

bool isMinHeap(int arr[],int size)
{
//code here
}

bool isMaxHeap(int arr[],int size)
{
//code here
}

int heapPlay(int arr[],int size)
{
//code here
}

Answer 1

#include <iostream>

using namespace std;

bool isMinHeap(int arr[],int size)

{

for (int i=0; i<=(size-2)/2; i++)

{

if (2*i+1 < size && arr[2*i +1] < arr[i])

return false;

if (2*i+2 < size && arr[2*i+2] < arr[i])

return false;

}

return true;

}

bool isMaxHeap(int arr[],int size)

{

for (int i=0; i<=((size-2)/2); i++)

{

if (2*i+1 < size && arr[2*i +1] > arr[i])

return false;

if (2*i+2 < size && arr[2*i+2] > arr[i])

return false;

}

return true;

}

int heapPlay(int arr[],int size)

{

if(isMaxHeap(arr,size) && isMinHeap(arr,size))

return 0;

else if(isMaxHeap(arr,size) || isMinHeap(arr,size))

return arr[0];

else

return -1;

}

int main() {

// int arr[] = {9,8,7};

// int size = 3;

// cout<<"IsMaxHeap: "<<isMaxHeap(arr,size) <<endl;

// cout<<"IsMinHeap: "<<isMinHeap(arr,size) <<endl;

// cout<<"Heap PLay: "<<heapPlay(arr,size)<<endl<<endl;

int arr2[] = {5};

int size2 = 1;

cout<<"IsMaxHeap: "<<isMaxHeap(arr2,size2) <<endl;

cout<<"IsMinHeap: "<<isMinHeap(arr2,size2) <<endl;

cout<<"Heap PLay: "<<heapPlay(arr2,size2)<<endl<<endl;

// int arr3[] = {1, 2 ,3};

// int size3 = 3;

// cout<<"IsMaxHeap: "<<isMaxHeap(arr3,size3) <<endl;

// cout<<"IsMinHeap: "<<isMinHeap(arr3,size3) <<endl;

// cout<<"Heap PLay: "<<heapPlay(arr3,size3)<<endl<<endl;

}

===========================================================================
See Output


Thanks