Fehlermeldung beim STL heap: Invalid heap



  • 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. 👍



  • 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?



  • 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?



  • 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?



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



  • 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?



  • 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. 😉



  • 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.



  • 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).



  • 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 🙂 👍


Anmelden zum Antworten