Fehlermeldung beim STL heap: Invalid heap



  • Guten Abend

    Ich wollte gerade einmal den heap aus der STL ausprobieren. Ich hatte dann das Problem, dass ich in meinem Code immer den Fehler "Invalid Heap" bekam. Daraufhin habe ich auf MSDN - heap folgenden Code gefunden:

    // heapfunc.cpp
    // compile with: /EHsc
    // 
    // Functions:
    //    make_heap : convert a sequence to a heap
    //    sort_heap : sort a heap
    //    push_heap : insert an element in a heap
    //    pop_heap  : remove the top element from a heap
    
    // disable warning C4786: symbol greater than 255 characters,
    // okay to ignore
    #pragma warning(disable: 4786)
    
    #include <iostream>
    #include <algorithm>
    #include <functional>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
        const int VECTOR_SIZE = 8 ;
    
        // Define a template class vector of int
        typedef vector<int > IntVector ;
    
        //Define an iterator for template class vector of strings
        typedef IntVector::iterator IntVectorIt ;
    
        IntVector Numbers(VECTOR_SIZE) ;
    
        IntVectorIt it ;
    
        // Initialize vector Numbers
        Numbers[0] = 4 ;
        Numbers[1] = 10;
        Numbers[2] = 70 ;
        Numbers[3] = 10 ;
        Numbers[4] = 30 ;
        Numbers[5] = 69 ;
        Numbers[6] = 96 ;
        Numbers[7] = 100;
    
        // print content of Numbers
        cout << "Numbers { " ;
        for(it = Numbers.begin(); it != Numbers.end(); it++)
            cout << *it << " " ;
        cout << " }\n" << endl ;
    
        // convert Numbers into a heap
        make_heap(Numbers.begin(), Numbers.end()) ;
    
        cout << "After calling make_heap\n" << endl ;
    
        // print content of Numbers
        cout << "Numbers { " ;
        for(it = Numbers.begin(); it != Numbers.end(); it++)
            cout << *it << " " ;
        cout << " }\n" << endl ;
    
        // sort the heapified sequence Numbers
        sort_heap(Numbers.begin(), Numbers.end()) ;
    
        cout << "After calling sort_heap\n" << endl ;
    
        // print content of Numbers
        cout << "Numbers { " ;
        for(it = Numbers.begin(); it != Numbers.end(); it++)
            cout << *it << " " ;
        cout << " }\n" << endl ;
    
        //insert an element in the heap
        Numbers.push_back(7) ;
        push_heap(Numbers.begin(), Numbers.end()) ;
    
        // you need to call make_heap to re-assert the
        // heap property
        make_heap(Numbers.begin(), Numbers.end()) ;
    
        cout << "After calling push_heap and make_heap\n" << endl ;
    
        // print content of Numbers
        cout << "Numbers { " ;
        for(it = Numbers.begin(); it != Numbers.end(); it++)
            cout << *it << " " ;
        cout << " }\n" << endl ;
    
        // remove the root element from the heap Numbers
        pop_heap(Numbers.begin(), Numbers.end()) ;
    
        cout << "After calling pop_heap\n" << endl ;
    
        // print content of Numbers
        cout << "Numbers { " ;
        for(it = Numbers.begin(); it != Numbers.end(); it++)
            cout << *it << " " ;
        cout << " }\n" << endl ;
    }
    

    Aber selbst bei diesem Code bekomme ich den Fehler "Invalid heap". Gemäss dem Call Stack passiert der Fehler in Zeile 75 bei

    push_heap(Numbers.begin(), Numbers.end()) ;
    

    Weiss jemand wo das Problem liegt?



  • Nach dem Aufruf von sort_heap() hast du keinen Heap mehr, sondern eine sortierte Liste, damit kann push_heap() nicht wirklich umgehen.

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



  • CStoll schrieb:

    Nach dem Aufruf von sort_heap() hast du keinen Heap mehr, sondern eine sortierte Liste, damit kann push_heap() nicht wirklich umgehen.

    Achso, das wusste ich nicht.

    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?

    Oder habe ich da etwas falsch vestanden?

    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.



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



  • 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