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

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

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 …

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] < …``````

## 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.