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(order != dontcare) {
        size_t heapsize = n;
        BuildMaxHeap(heapsize);
        for(size_t i = size()-1; i >= 1; i--) {
            swap(a[0], a[i]);
            heapsize--;
            heapify(0, heapsize);
        }
        else if(order == ascending) {
            for (int i = 0; i < (HEAP<E>::n+1); ++i) {
                ++rc;
                if(!f(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;	
}

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

CStoll

Was für Werte kann denn order haben? Abgesehen davon, daß der Code etwas unregelmäßig formatiert ist, scheinen dort ein paar Klammern zu fehlen.

Klammern fehlen keine. Die Formatierung ist schon etwas unregelmäßig, dafür möchte ich mich herzlichst entschuldigen. Aber ich hatte etwas Streß, währrend ich den Thread erstellt habe.

Nun zum eigentlichen, order kann den Wert ascending, descending oder dontcare einnehmen. Dontcare und descending funktionieren. Wie oben beschrieben wird beim ersten Durchlauf der Methode, wenn ascending gewählt word korrekt sortiert und beim zweiten Mal hackt es, aber da auch "nur" bei den ersten beiden Einträgen nach der Wurzel.

CStoll

Ich war mal so frei, die Formatierung ein wenig geradezubiegen. Und jetzt sieht man auch deutlich, daß zu dem else in Zeile 11 das if() fehlt.
Ansonsten: Das erste if() gilt sowohl für ascending als auch für descending und wie du den Unterschied der Sortierrichtung einarbeitest kann ich nicht so richtig erkennen (theoretisch müsste schon der heapify()-Aufruf die Richtung berücksichtigen).

Ich wollte den Code eigentlich kürzen, um ihn übersichtlicher zu machen, weil es ja vorher zu viel war.

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

	size_t rc = 0;

	if(order != dontcare) {
             size_t heapsize = n;
             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>::heapify(size_t i, size_t heapsize) const{
     size_t left = 2*i + 1;
     size_t right = 2*i + 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);
     }
}[/code]

Ich hoffe, dass es diesmal nicht wieder zu viel Code ist, aber für das Verständnis des Ablaufes benötigt man meiner Meinung nach beide Methoden. heapify() stellt die Heapbedingung für einen Max-Heap wieder her.

CStoll

Es ist sicher nicht zu viel Code, um dein Problem zu erklären, aber auf Anhieb zu viel Code, um ihn als Außenstehender verarbeiten zu können. Hat es einen Grund, warum du dein HeapSort selber implementiert hast? Die STL bietet schon ein ca. halbes Dutzend fertige Funktionen, um eine Datensammlung sortieren zu können.

Was noch auffällt: Beim Sortieren des Arrays arbeitest du mit n Elementen, bei der Ausgabe verwendest du n+1 als Randbedingung.

An sich hab ich den Heapsort so implementiert, weil ich von den VO Unterlagen nicht zu weit abweichen wollte. Aber über eine einfachere Möglichkeit wäre ich auch nicht unglücklich. Kannst du mir eine STL empfehlen für die Sortierung? Die Randbedingungen prüfe ich morgen früh sofort noch einmal prüfen, aber der heap an sich haben zuvor schon vollständig funktioniert, denn ich habe das File schon mal abgegeben und mein Prof hat mir zusätzlich eine inplace Sortierung aufgegeben.

CStoll

tinkabell schrieb:

Kannst du mir eine STL empfehlen für die Sortierung?

"eine" STL wird schwierig STL steht für "Standard Template Library" und ist ein Teil der C++ Standardbibliothek. Wenn es dir nicht um die pädagogische Herausforderung geht, verwende einfach std::sort() (das verwendet zwar idR QuickSort, aber für den erwarteten Effekt ist das egal), ansonsten kannst du dir auch std::make_heap() und std::sort_heap() ansehen.
(alle drei Funktionen findest du in der <algorithm>)

PS: Afair ist ein Heap zwar gut geeignet, um schnell das größte Element einer Sammlung zu finden, aber das ständig Auf- und Abbauen des Heaps geht auch auf die Rechenzeit.

Eisflamme

Aber wieso hilft das. Da steht doch, er muss für die Uni nen Heapsort schreiben.

314159265358979

CStoll schrieb:

das verwendet zwar idR QuickSort, aber für den erwarteten Effekt ist das egal

Ich weiß nicht, wie das beim GCC ist, aber bei MSVC ists ein Introsort. (Je nach Anzahl entweder Insertion Sort, Quicksort oder Heapsort)

Also sort() oder sort_heap(), darf ich nicht verwenden. Das hat mir die Uni untersagt. Ich muss jeden Vorgang selbst ausprogrammieren.

Die Randbedingungen sind in Ordnung. Hab das ganze noch einmal überprüft.

Zur Veranschaulichung eine Aussage (ascending):
> apply asc
1 3 5 7 9
returns 5
> apply asc
1 5 3 7 9
returns 5

und im absteigenden Verfahren (descending):
> apply desc
9 7 5 3 1
returns 5
> apply desc
9 7 3 5 1

Irgendwo im Sortierungsablauf muss sich ein Fehler eingeschlichen haben. Aber ich kann nicht genau lokalisieren wo.

Please, please help me!!