Question

C++

Given a sequence of integers, check to see if the sequence constitutes a heap

Input: the first line is an integer n(0 < n < 10000), The second line is n integers

Output: If the sequence is a very small heap, that is, the top of the heap is the smallest element, then output "min heap". If the sequence is a very large heap, the top of the heap is the largest element

The output includes one line with a newline at the end

Example:

## Input

5

3 4 2 1 1

##Output:

no

Answer 1

Output

#1

#2

#3

Code with comments

#include<bits/stdc++.h>

using namespace std;

void checkMinHeap(vector<int>&v){   //check for min heap

    int n=v.size();

    for(int i=0;i<n;i++){

        int left = 2*i+1;   //left child

        int right = 2*i + 2;    //right child

        if(left<n && v[i]>v[left]){ //check root i greater then left

            cout<<"No";

            return;

        }

        if(right<n && v[i]>v[right]){  //check root i greater then right

            cout<<"No";

            return;

        }

    }

    cout<<"Min heap";

}

void checkMaxHeap(vector<int>&v){  //check for max heap

    int n=v.size();

    for(int i=0;i<n;i++){

        int left = 2*i+1;

        int right = 2*i + 2;

        if(left<n && v[i]<v[left]){  //check root i less then left

            cout<<"No";

            return;

        }

        if(right<n && v[i]<v[right]){  //check root i less then right

            cout<<"No";

            return;

        }

    }

    cout<<"Max heap";

}

int main(){

    int n;

    cin>>n;

    vector<int>v(n);

    for(int i=0;i<n;i++){

        cin>>v[i];

    }

    if(v[0]>v[1]) checkMaxHeap(v);  //check which function to call

    else checkMinHeap(v);

}

For indentation purpose