473,890 Members | 2,051 Online

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

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(Iterat or 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(Itera tor 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
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.
Jul 22 '05 #1
0 1388

This thread has been closed and replies have been disabled. Please start a new discussion.