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!

Recommended Answers

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 …

Jump to Post

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] < …
Jump to Post

All 5 Replies

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

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

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

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?

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;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.