Check If an Array Represents a Max Heap (Danny Heap Algorithm)

Given a list of integers nums, return whether it represents a max heap. That is, for every i we have that:
nums[i] ≥ nums[2*i + 1] if 2*i + 1 is within bounds
nums[i] ≥ nums[2*i + 2] if 2*i + 2 is within bounds

Example 1
Input
nums = [4, 2, 3, 0, 1]
Output
true

Max Heap Check Algorithm

Intuitively we go through the array once and check if the corresponding requirement satisfy for the left/right node. We have to check if the index is within the given bounds.

bool checkMaxHeap(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++ i) {
        if ((2 * i + 1 < nums.size()) && (nums[i] < nums[i * 2 + 1])) {
            return false;
        }    
        if ((2 * i + 2 < nums.size()) && (nums[i] < nums[i * 2 + 2])) {
            return false;
        }
    }
    return true;
}

We can reverse the heap checks from right to left. Both implementation takes O(N) time and O(1) space.

bool checkMaxHeap(vector<int>& nums) {
    for (int i = nums.size() - 1; i >= 1; -- i) {
        int a = (i - 1) / 2;
        if (nums[a] < nums[i]) return false;
        int b = (i - 2) / 2;
        if ((b >= 0) && (nums[b] < nums[i])) return false;
    }
    return true;
}

Another small improvemnt is to limit the search to half range:

bool checkMaxHeap(vector<int>& nums) {
    for (int i = 0; i * 2 + 1 < nums.size(); ++ i) {
        int a = (i << 1) + 1;
        if (nums[i] < nums[a]) {
            return false;
        }
        if (a + 1 < nums.size() && (nums[i] < nums[a + 1])) {
            return false;
        }
    }
    return true;
}

In A Max Heap, the value of the root node is always larger than the descendents.

–EOF (The Ultimate Computing & Technology Blog) —