Heap

[irpersian20]

Hi,
Write an algorithm that determines whether or not an almost complete binary tree is a heap.
Please

[BioPhysEngr]

You won't find people willing to do your work for you. However, we can help you write an algorithm.

What have you got so far and what is giving you difficulty?

This link may help: https://en.wikipedia.org/wiki/Heap_%28data_structure%29

[nuzzle]

Write an algorithm that determines whether or not an almost complete binary tree is a heap.

Isn't it just to visit each node of the binary tree and check the heap property and if it is satisfied for all nodes the tree is a heap?

[irpersian20]

// input: an array of size n

isHeap(array h, index i) {

      if(i > n/2) return true;   //base case

      if(h[i*2+1]!= null) {

            if((h[i] >= h[i*2]) && (h[i] >= h[i*2+1]))

                  isHeap(h, i+1);

            else

                  return false;

      }

      else {

            if(h[i] >= h[i*2])

                  isHeap(h, i+1);

            else

                  return false;

      }

}

The above algorithm is correct or incorrect ?

[BioPhysEngr]

Hrm, I have not encountered a tree represented as a linear array before. I believe the idea you have is (mostly) correct:

First, I think your array indices for children are not correct. I think the children of a node, i, are given by:

2*i+1
and
2*i + 2

Second, the recursion step should be to the children; that is, the statements should be:

return isHeap(h, 2*i+1) && isHeap(h, 2*i+2);

But I am just reasoning abstractly. Someone (nuzzle?) want to check me?

[Peter_B]

Hrm, I have not encountered a tree represented as a linear array before. I believe the idea you have is (mostly) correct:

First, I think your array indices for children are not correct. I think the children of a node, i, are given by:

2*i+1
and
2*i + 2

Using a linear array to represent the heap is useful in this case as it guarantees the 'shape' property is fulfilled (i.e. that the terminal nodes are on at most two levels, with those on the bottom level being filled in from the left).
This representation is used in the chapter on Heaps in Programming Pearls by Jon Bentley.

He uses a 1-based array, giving the children as 2i and 2i+1 (which is what irpersian20 is using), but for a 0-based array (which is presumably what we are using here) it should indeed be 2i+1 and 2i+2 as BioPhysEngr says.

[BioPhysEngr]

Thanks for the better clarification, Peter. I was suspecting a 0-vs-1-based array issue, but didn't want to cause any confusion (in case I was wrong).

irpersian20, does that help some?

[nuzzle]

Hrm, I have not encountered a tree represented as a linear array before.

It's used in Heapsort. It builds a max-heap as part of the sorting process.

The root node conventionally is put at index 1 in this kind of heap implementations because this leads to the cheapest child and parent index calculations using just shifts and additions. So it's probably best to stick to this index convention in the algorithm and then subtract 1 when the array is accessed if one wants the root at 0.

To check whether a heap is a max-heap the OP needs to visit all non-leaf nodes and make sure each is bigger than its children. I think this can be done in a recursive traversal as you suggest but also iteratively. That's what the OP attempting. It's really an iterative solution.

[nuzzle]

The above algorithm is correct or incorrect ?

Although recursive, what you have here really is an iterative approach in disguise.

I don't have time to check it out right now but there's an immediate problem - isHeap doesn't always return a value. To fix it change both recursive calls to this,

return isHeap(h, i+1);

I suggest you implement the algorithm in real code and then try it out on a few test heaps. Then you'll see if it works or not.

[nuzzle]

This is a basic iterative implementation. It simply checks that each parent is bigger than its children.

The only assumption is that if a child index falls outside N there exists no child (and 0 is used to denote that).

I'm sure this can be optimized. For example I think only nodes up to index N/2 can be parents so only they would have to be checked. And I think if there is no left child there can be no right child so it wouldn't have to be checked in that case.

int left(int i, int N) { // return left child index or 0 if it doesn't exist
	i = 2*i;
	return i<=N ? i : 0;
}
int right(int i, int N) {  // return right child index or 0 if it doesn't exist
	i = 2*i+1;
	return i<=N ? i : 0;
}
//
bool isHeap(int a[], int N) {
	for (int i=1; i<=N; ++i) { // all nodes
		int l = left(i,N); // left child
		if (l>0) // if there's a left child
			if (a[i]<a[l]) return false; // it must be smaller than this node
		int r = right(i,N); // right child
		if (r>0)  // if there's a right  child
			if (a[i]<a[r]) return false;  // it must be smaller than this node
	}
	return true; // all nodes passed the max test
}
//
void test() {
	const int N=10; // 10 elements
	int a[N+1] = {-1,9,6,4,5,5,3,2,1,1,4}; // max-heap, index 0 isn't used
	std::cout << (isHeap(a, N) ? "yes" : "no") << std::endl;
}

[Peter_B]

I'm sure this can be optimized. For example I think only nodes up to index N/2 can be parents so only they would have to be checked.

Yes, the last node which is a parent is that which is parent of the last entry in the array. So this will be node floor(N/2) (for 1-based arrays).

The form of the tree (i.e. it has the 'shape' property - the terminal nodes are on at most two levels, with those on the bottom level being filled in from the left) is such that you can guarantee that all nodes before this last parent will have both left and right children.

This gives us a useful way to optimise, as the loop over all but the last parent does not have to check if the children exist - they are guaranteed to exist. We therefore can save time by accessing them without checking they exist first.

Then, check the last parent separately - this is guaranteed to have a left child, but may or may not have a right child.