Help Please: Finding out the Iterator to the Child node in binary heap

C

CoolPint

I am trying to write a generic heapsort (of course as a self-exercise)
with Iterator interface: something like blow....

But I got into trouble finding out the Iterator to the Child node. If
indexing was used, I could do something like child = hole * 2 + 1; but
since only thing the function accepts are random access Iterators, how
do I calculate the Iterator to the child node?

template <typename Iterator, typename Functor>
void heapsort(Iterator begin, Iterator end, Functor cmp)
// I assume that begin and end are random access iterators
{
int noleafOffset = (end -1 - begin) / 2;
// since end is the iterator to one past the last one

for (Iterator i = begin + noleafOffset; i >= begin; i--)
shiftdown(i, end-1, cmp);
for (Iterator j = end - 1; j > begin; j--) {
swap (*begin, *j);
shiftdown(begin, j, cmp);
}
}

The problem is making "shiftdown" function template work with
Iterator.

template <typename Iterator, typename Functor>
void shiftdown(Iterator top, Iterator bottom, Functor cmp)
{
Iterator hole = top;
----->> Iterator child = hole * 2 + 1; // This is the problem!
// I know I cannot apply operator*() to an Iterator so how do I
find an
// Iterator to the left child?

while ( bottom >= child) {
if (child != bottom && cmp( *(child + 1), *child) )
child++;
if ( cmp( *child, *bottom)) {
*hole = *child;
hold = child;
----->> child = hole * 2 + 1;
// Again, how do we find out the Iterator to child?
}
else break;
}
*hole = *bottom;
}

template <typename T>
void swap(T & a, T & b)
{
T temp = a;
a = b;
b = temp;
}

Can I not implement the generic heapsort template accepting only
iterators to first element and one past the last element? Please help.
Thank you in advance. BTW, I could write bubblesort, quicksort based
on this interface. I think the problem is my lack of understanding
certain features, logic, etc... I would very much appreciate any
suggestion.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top