max-HEAP Functor-Aufruf #1 mit falschem key 4711 (statt 666);

Hallo Leute,

ich muss für die Uni einen Heap mit Heapsort (Max-Heap) programmieren. Mein konkretes Problem, wie man oben sieht liegt in der apply Methode. Der Fehler wird, dass habe ich schon heraus gefunden, ausgeworfen, weil bei jedem zweiten Aufruf von apply ascending der zweite und der dritte Wert immer vertauscht sind. Absteigend sortieren funktioniert einwandfrei. Ich weiß natürlich, dass es irgendwo in der Sortierung liegen muss, aber wie sich der Fehler einschleicht kann ich mir nicht erklären, weil sie ja bei jedem ersten Versuch richtig funktioniert.

//////////////////////////////////////////////////////////////////////////
template <typename E>
size_t HEAP<E>::apply(const Functor<E>& f, Order order) const {
if(HEAP<E>::n == -1) { //Container leer
return 0;
}

size_t rc = 0;

if(order != dontcare) {

size_t heapsize = n; //n = Anzahl der Werte im Heap
BuildMaxHeap(heapsize);
for(size_t i = size()-1; i >= 1; i--) {
swap(a[0], a[i]);
heapsize--;
heapify(0, heapsize);
}

if(order == descending) {
for (int i = (HEAP<E>::n+1); i-- > 0; ) {
++rc;
if(!f(a[i]))break;
}
}

else if(order == ascending) {
for (int i = 0; i < (HEAP<E>::n+1); ++i) {
++rc;
if(!f(a[i]))break;
}

}
}

else if(order == dontcare) {
for(int i=0; i < (HEAP<E>::n+1); i++) {
++rc;
if(!f(HEAP<E>::a[i]))break;
}
}

int heapgroesse = n;

if(a[n]>a[0]) {
swap(a[0],a[n]);

for(size_t i=1; i<size(); i++) {
heapify(i, heapgroesse);
}
}

return rc;
}
//////////////////////////////////////////////////////////////////////////

template <typename E>
void HEAP<E>::BuildMaxHeap(size_t zaehler) const{
for(size_t i= zaehler/2-1; i>0; i--) {
heapify(i, zaehler);
}
}
//////////////////////////////////////////////////////////////////////////

template <typename E>
void HEAP<E>::heapify(size_t i, size_t heapsize) const{
size_t left = 2i + 1;
size_t right = 2i + 2;
size_t largest;

if (left < heapsize && a[left] > a[i]) {
largest = left;
}

else
largest = i;

if (right < heapsize && a[right] > a[largest]) {
largest = right;
}

if (largest != i) {
swap(a[i], a[largest]);
heapify(largest, heapsize);
}
}
//////////////////////////////////////////////////////////////////////////

Alles andere funktioniert und meine Literatur ist mittlerweile auch schon erschöpft. Kann mir vielleicht irgendwer weiterhelfen?

pumuckl

Lies dir bitte den Link in meiner Signatur durch und poste deinen Code nochmal mit Code-Tags und aufs Wesentliche reduziert. So ist das ein ziemlicher krampf, das zu lesen