heap function

[marnun]

We started learning Heap property in class. Here is an exercise on the topic:

isHeap
Write the definition of a function named isHeap that receives three arguments as follows:
x : an array of ints
i : a valid index into the array x
n : the number of elements in the array x

The function returns true if the HEAP property holds among the array elements x[i]...x[n-1] , and false otherwise. The HEAP property is simply that for every value of j between i and n-1 , x[j] is not less than its heap children if they exist. (The heap children of x[j] are x[2j+1] and x[2j+2] .

My code:

bool isHeap (int x[], int n, int i) {
    bool heap=true;
    for (int j=i; j<n; j++) {
        if ((2*j+1)<=(n-1)) {
            if (x[j]>=x[2*j+1]&&x[j]>=x[2*j+2])
                heap=true;
            else
                heap=false;
        }
        else
            heap=true;
        return heap;
    }
}

CodeLab returns logical error:

Remarks:
     ⇒     fails for:
     ⇒     starting point: 0
     ⇒     5 elements: 50 50 50 50 50

     ⇒     Your code had an error during execution

I have a feeling it's something about correctness of boolean logic but can't see it right now..
Any suggestions?
Thanks!

[nullptr]

The function returns true if the HEAP property holds among the array elements x[i]...x[n-1] , and false otherwise. The HEAP property is simply that for every value of j between i and n-1 , x[j] is not less than its heap children if they exist. (The heap children of x[j] are x[2j+1] and x[2j+2] .

So basically x[j] can have 0, 1 or 2 children. If it has no children, then there's nothing to cause a HEAP property failure. For code efficiency, there's no reason to check for a second child unless x[j] has a first child and the HEAP property holds true for the first child.

So with that in mind, the 'pseudo' code would look like:

bool isHeap (int* x, int n, int i) 
{
    for (int j = i; j < n; j++) 
    {
        if (first child exists)
        {
            if (x[j] < x[first child])
                return false;

            if (second child exists) 
            {
                if (x[j] < x[second child])
                    return false;
            }
        }
    }

    return true;
}

[nullptr]

This can be further optimized because if x[j] has no first child, then obviously on the next loop x[j + 1] would have no children. So you can just break if the first child doesn't exist.

if (!first child exists)
    break;
else
{
    if (x[j] < x[first child])
        return false;
    if (second child exists)
    {
        if (x[j] < x[second child])
            return false;
    }
}

[nullptr]

Revised pseudo code:

bool isHeap (int* x, int n, int i) 
{
    for (int j = i; j < n; j++) 
    {
        if (!(first child exists))
            break;
        if (x[j] < x[first child])
            return false;
        // if no second child, there'll be no
        //  first child in the next loop, so break
        if (!(second child exists)) 
            break;

        if (x[j] < x[second child])
            return false;
    }

    return true;
}

[marnun]

Thank you for suggestion.
Here is the implementation of your pseudo code:

bool isHeap (int x[], int n, int i) {
    for (int j=i; j<n; j++) {
        if ((2*j+1)>(n-1))
            break;
        if (x[j]<x[2*j+1])
            return false;
        if ((2*j+2)>(n-1))
            break;
        if (x[j]<x[2*j+2])
            return false;
    }
    return true;
}

CodeLab still returns the same logical error. Did I miss something?

[marnun]

I adjusted code a little bit, and switched order of 2nd and 3rd parameters according to the specs of the exercise, and now it's working. thank you, nullptr, for your guidance.

bool isHeap (int x[], int i, int n) {
    for (int j=i; j<n; j++) {
        if ((2*j+1)<n) {
            if (x[j]<x[2*j+1])
                return false;
        }
        if ((2*j+2)<n) {
            if (x[j]<x[2*j+2])
                return false;
        }
    }
    return true;
}