ronith
9/7/2018 - 4:53 AM

Does array represent Heap

Given an array, how to check if the given array represents a Binary Max-Heap.

Examples:

Input: arr[] = {90, 15, 10, 7, 12, 2} Output: True The given array represents below tree 90 /
15 10 / \ / 7 12 2 The tree follows max-heap property as every node is greater than all of its descendants.

Input: arr[] = {9, 15, 10, 7, 12, 11} Output: False The given array represents below tree 9 /
15 10 / \ / 7 12 11 The tree doesn't follows max-heap property 9 is smaller than 15 and 10, and 10 is smaller than 11.

Does array represent Heap.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/how-to-check-if-a-given-array-represents-a-binary-heap/
#include <iostream>
using namespace std;

bool isHeap (int a[],int i, int n) {
    int l= 2*i+1, r= 2*i+2;
    if (l<n && r<n) {
        if (a[i] > a[l] && a[i] > a[r] && isHeap(a, l, n) && isHeap (a, r,n))
            return 1;
        else
            return 0;
    }
    else if (l<n) {
        if (a[i] > a[l] && isHeap(a, l, n))
            return 1 ;
        else
            return 0;
    }
    return 1;
}

int main() {
    int t;
    cin>>t;
    while (t-->0) {
        int n;
        cin>>n;
        int a[n];
        for (int i=0;i<n;i++)
            cin>> a[i];

        cout<< isHeap(a,0, n) << "\n";
    }
}