Home
Check If an Array Represents a Max Heap (Danny Heap Algorithm)
Tags:, , ,

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

November 22, 2020 No Comments algorithms, c / c++, data structure

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.

1
2
3
4
5
6
7
8
9
10
11

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;
}
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.

1
2
3
4
5
6
7
8
9

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;
}
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:

1
2
3
4
5
6
7
8
9
10
11
12

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;
}
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) —

GD Star Rating
loading...
343 words
Last Post: Teaching Kids Programming - Recursion in Five Minutes
Next Post: Teaching Kids Programming - From Linear Search to Binary Search Algorithm

The Permanent URL is: Check If an Array Represents a Max Heap (Danny Heap Algorithm)

Related posts:

  1. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  2. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  3. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  4. Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A...
  5. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  6. Depth First Search Algorithm to Check If Two Expression Trees are Equivalent A binary expression tree is a kind of binary tree used to represent arithmetic expressions....
  7. How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)? Given a binary search tree and the lowest and highest boundaries as L and R,...
  8. A Simple Function to Perform Integer/Float Arithmetic Calculation via AWK The inbuilt BASH does not support floating point arithmetic calculations but we can easily declare...

Leave a Reply