Heap: Given an array, check if the array represents Binary Max Heap

Problem Statement:

You are given an array, you need to check if the array represents Binary Max Heap

Example:

Input: arr = {7, 3, 6, 1, 2, 4, 5}

Solution Explanation:

Write the iterative solution

Time Complexity: O(n)
Space Complexity: O(h)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

bool solution(vector<int> arr) 
{   
    int n = arr.size();

    //start from the last non leaf node
    // check if each parent node is greater than its children
    for (int i = (n / 2 - 1); i >= 0; i--) 
    {
        if (arr[i] < arr[2 * i + 1])
            return false;

        if (2 * i + 2 < n && arr[i] < arr[2 * i + 2])
            return false;
    }
    return true;
}

int main() 
{
    vector<int> arr = {7, 3, 6, 1, 2, 4, 5};

    if (solution(arr))
    	cout<< "True"<<endl;
    else
    	cout<< "False"<<endl;
    return 0;
}

Output

True