By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,804 Members | 1,681 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,804 IT Pros & Developers. It's quick & easy.

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

P: n/a
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

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) )
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
Jul 22 '05 #1
Share this question for a faster answer!
Share on Google+

This discussion thread is closed

Replies have been disabled for this discussion.