How to check if a given array represents a Binary Heap? - GeeksforGeeks
An Iterative Solution is to traverse all internal nodes and check id node is greater than its children or not.
Read full article from How to check if a given array represents a Binary Heap? - GeeksforGeeks
Given an array, how to check if the given array represents a Binary Max-Heap.
A Simple Solution is to first check root, if it’s greater than all of its descendants. Then check for children of root. Time complexity of this solution is O(n2)
An Efficient Solution is to compare root only with its children (not all descendants), if root is greater than its children and same is true for for all nodes, then tree is max-heap (This conclusion is based on transitive property of > operator, i.e., if x > y and y > z, then x > z).
bool isHeap(int arr[], int i, int n){ // If a leaf node if (i > (n - 2)/2) return true; // If an internal node and is greater than its children, and // same is recursively true for the children if (arr[i] >= arr[2*i + 1] && arr[i] >= arr[2*i + 2] && isHeap(arr, 2*i + 1, n) && isHeap(arr, 2*i + 2, n)) return true; return false;}// Function to handle array boundint getVal(int arr[], int idx, int n){ if (idx < n) return arr[idx]; else return INT_MIN;}// Returns true if arr[i..n-1] represents a// max-heapbool isHeap(int arr[], int i, int n){ // Base case if (i >= n - 1) return true; // If root is greate than its children and // same is recursively true for the children if (arr[i] >= getVal(arr, 2*i + 1, n) && arr[i] >= getVal(arr, 2*i + 2, n) && isHeap(arr, 2*i + 1, n) && isHeap(arr, 2*i + 2, n)) return true; return false;}bool isHeap(int arr[], int n){ // Start from root and go till the last internal // node for (int i=0; i<=(n-2)/2; i++) { // If left child is greater, return false if (arr[2*i +1] > arr[i]) return false; // If right child is greater, return false if (arr[2*i+2] > arr[i]) return false; } return true;}