Level Order in Heap (with a twist)

[dolfan55aj]

We have to do a level order traversal of a max-heap and I'm having some trouble. Of course a regular level order traversal in a heap is easy as can be (it's an array of course) but now I have to print it in a sort of tree structure. For example if I have a heap with the following values [9, 5, 6, 4, 3, 2] I have to print it as follows:

9
5 6
4 3 2

Right now here's my code for a simple level order:

template<class ItemType>
void BinaryHeap<ItemType>::PrintLevel(ostream &out)
{
	out << endl;
	for(int i=1; i <= currentSize; i++)
	{
		out << BHeap[i] << " ";
	}
}

Anybody have any ideas or tips on how to do this? I just can't seem to figure out the logic on when I'm going to need to do and endl;... Let me know if you can, Thanks!

[vijayan121]

The number of entries at each level in a binary heap is a power of two; 1, 2, 4, 8, ...and so on ( 2^N starting with N==0 ).

So you need to put a new line to start the next level after 1, 3, 7, 15 and so on. ie. after every 2^(N-1) entries starting with N==1.