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!

2
Contributors
1
Reply
4
Views
6 Years
Discussion Span
Last Post by 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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.