Fehlermeldung beim STL heap: Invalid heap

CStoll

icarus2 schrieb:

Sehe ich das richtig, dass ein push mit
heap.push_back( x->rect );
std::push_heap( heap.begin(), heap.end() );
und ein pop mit
std::pop_heap( heap.begin(), heap.end() );
x_data.pop_back();
gemacht wird?

Ja, das kommt hin (abgesehen davon, daß die letzte Zeile wohl heap.pop_back() heißen sollte) - wenn du das Element noch weiterverarbeiten willst, mußt du es vor dem pop_back() sichern.

CStoll schrieb:

PS: konntest du die Test-Ausgaben nicht in eine Funktion auslagern?

Das haben die Leute von Microsoft verbrochen... ich hab das Codebeispiel 1:1 von der Website kopiert.
Toll, dass dort Code steht, der nicht funktioniert.

Kannst dich ja dort beschweren Vermutlich wollten sie nur einfach alle heap-Funktionen in ein Beispiel quetschen - oder sie haben das Beispiel nur mit einer STL-Version ohne diese Fehlerkontrolle übersetzt.
(ideone und codepad schlucken das Beispiel auch ohne zu murren)

icarus2

Ja, da müsste heap stehen

Es scheint jetzt mehr oder weniger zu laufen. Irgend etwas ist noch nicht ganz richtig in meinem Code. Bin jetzt aber zu müde. Ich werde mich dann morgen drum kümmern.

Danke für die Hilfe.

icarus2

Ich habe nun das Problem, dass ich aus dem Heap ein beliebiges Element entfernen möchte. Ich habe einen Heap, der nur int-Werte enthält. Nun möchte ich z.B. den Wert 7 aus dem Heap entfernen. Wie gehts das?

drakon

Das ist nicht der Sinn eines Heaps. Man benutzt den Heap dazu Minima oder Maxima effizient zugänglich zu machen.
Warum musst du da etwas anderes als Maxima/Minima entfernen?

icarus2

Ich habe eine Menge von Rechtecken gegeben, die definiert sind durch x_links, x_rechts und die Höhe.
Ich habe dann die x_links und x_rechts in einem vector sortiert. Den Heap brauche ich in meiner Scanline. Wenn ein neues x_links kommt, soll die dazugehörige Höhe eingefügt werden, bei x_rechts entfernt werden aus dem max heap.

Es geht darum die Fläche zu berechnen, die die Rechtecke abdecken. Deshalb brauche ich stets die maximale Höhe. Darum habe ich an einen max heap gedacht.

Aber stimmt, wenn ich mich recht erinnre eignet sich ein Heap nur um das Maximum zu entfernen, nicht irgend einen Wert, oder?

drakon

Ok. Da kannst du den schon benutzen. Mit decreaseKey und deleteMin (respektive increaseKey und deleteMax ;)).

icarus2

Ich verstehe nicht ganz. Ich nehme mal an, dass das Funktionen der STL sind aber ich habe nichts darüber gefunden. Kannst du mir kurz erklären wie die funktionieren oder sagen wo ich etwas darüber finde?

drakon

Nein. Die gibt es eben nicht in der STL. Aber Heaps sehen diese Funktion theoretisch zumindest vor.

Implementieren kannst du das doch auch ohne gross die theoretisch optimalen Strukturen zu nehmen. Nimm doch einfach einen sortieren vector, um die Höhen zu verwalten. Worstcase optimal wird das dann nicht, aber du wirst auch kaum so grosse Testcases haben, dass das eine Rolle spielt.

icarus2

Achso. Ja ich schau mal wie ich das am besten mache.

Habe gerade noch den Artikel von Jester gefunden: http://www.c-plusplus.net/forum/180990

Werde mir den mal durchlesen. Vielen Dank.

drakon

Gute Idee.
Ist btw. eine beliebte Aufgabe bei der Prüfung Heaps zu manipulieren (Array in einen Heap zu überführen oder auch die Operationen von Hand zu machen).

icarus2

drakon schrieb:

Gute Idee.
Ist btw. eine beliebte Aufgabe bei der Prüfung Heaps zu manipulieren (Array in einen Heap zu überführen oder auch die Operationen von Hand zu machen).

Gut zu wissen, danke