Help Please: Finding out the Iterator to the Child node in binary heap
From: CoolPint (coolpint_at_yahoo.co.uk)
Date: 12/18/03
- Next message: Gianni Mariani: "Re: Two pointers to the same obejct, two differnet values..."
- Previous message: Alf P. Steinbach: "Re: Two pointers to the same obejct, two differnet values..."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 18 Dec 2003 06:42:10 -0800
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.
- Next message: Gianni Mariani: "Re: Two pointers to the same obejct, two differnet values..."
- Previous message: Alf P. Steinbach: "Re: Two pointers to the same obejct, two differnet values..."
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
