Heap mit STL implementieren



  • Hallo,

    Ich versuche gerade unter Verwendung der STL einen Heap zu erzeugen. Ich hab mir dafür eine priority_queue hergenommen und es funktioniert auch alles prima:
    Elemente einfügen, pushen und poppen...alles korrekt sortiert.
    Allerdings muß ich im Laufe meines Algos beliebige Elemente aus dem Heap updaten (d.h. deren Priorität kann sich ändern).
    Und hier stößt die PQ auch schon an ihre Grenzen. Sie verfügt über keinerlei Updatefunktion, oder seh ich das falsch?

    Gibt es einen anderen schönen Weg mit der STL eine Heapstruktur zu halten?

    Grüße,
    Heiko



  • brotmachine schrieb:

    Hallo,

    Ich versuche gerade unter Verwendung der STL einen Heap zu erzeugen. Ich hab mir dafür eine priority_queue hergenommen und es funktioniert auch alles prima:
    Elemente einfügen, pushen und poppen...alles korrekt sortiert.
    Allerdings muß ich im Laufe meines Algos beliebige Elemente aus dem Heap updaten (d.h. deren Priorität kann sich ändern).
    Und hier stößt die PQ auch schon an ihre Grenzen. Sie verfügt über keinerlei Updatefunktion, oder seh ich das falsch?

    Gibt es einen anderen schönen Weg mit der STL eine Heapstruktur zu halten?

    Grüße,
    Heiko

    Priority queue ist wohl ein STL-Container?

    Dann kannst du einfach nen Iterator auf das zu ändernde Element setzten (it = queue.begin()+irgendwas) und dann das Element setzten

    *it = updated_value;



  • Wie der Name schon sagt - es ist eine Queue. Man kommt nicht an die einzelnen Elemente. Und priority_queue ist ein STL-Container-Adapter. Der Standardcontainer ist (ich weiß es nicht genau) vector, man kann ihn aber durch einen anderen ersetzen.

    Eine priority_queue sollte für einen Heap nicht unbedingt geeignet sein - da sie mehr macht, als für einen Heap erforderlich ist. So erfüllen z.B. die Wertefolgen 5 4 3 und 5 3 4 das Heap-Kriterium. Die priority_queue lässt aber nur 5 4 3 zu. Es ist zwar nicht 'schädlich', aber mehr als man erwartet. Und wie gesagt, da sie den Zugriff auf Einzelelemente nicht zulässt, sollte sie für deine Einfügeoperationen nicht geeignet sein.

    Ich würde mal schauen, ob es bereits schöne Heap-Container-Adapter gibt.



  • Harry Hirsch schrieb:

    So erfüllen z.B. die Wertefolgen 5 4 3 und 5 3 4 das Heap-Kriterium. Die priority_queue lässt aber nur 5 4 3 zu.

    hä?
    warum das denn?



  • Was ich noch gefunden habe:
    Man kann andere STL-Container mit make_heap in einen Heap umwandeln. Dazu müßte ich aber noch die Sortierbedingung mit angeben und habe noch nicht so recht geschnallt wie.

    Mal die grobe Idee:

    [i]// die Elemente für den Heap[/i]
    struct FMBandElement 
    {
      Vector pos;
      int distance;
    };
    
    [i]// vector von pointern auf die Elemente[/i]
    std::vector<FMBandElement* >
    

    Ich will die Elemente im Heap nach ihrer distance sortieren.

    Was make_heap macht:

    template<class RanIt, class Pred>
        void make_heap(RanIt first, RanIt last, Pred pr);
    

    Mein Problem ist momentan eigentlich nur: Wie definier und übergeb ich den Vergleichsoperator?



  • brotmachine schrieb:

    Mein Problem ist momentan eigentlich nur: Wie definier und übergeb ich den Vergleichsoperator?

    Ein kleines Beispiel:

    struct Edge_Table_Elem {
    	double ylower;
    	double xlower;
    	double yupper;
    	double reverse_slope;	// 1/m
    	bool operator>(const Edge_Table_Elem& other) const { 
    		return ( ylower > other.ylower ); 
    	} 
    	bool operator<(const Edge_Table_Elem& other) const { 
    		return( ylower < other.ylower ); 
    	} 
    };
    


  • brotmachine schrieb:

    Hallo,
    Ich versuche gerade unter Verwendung der STL einen Heap zu erzeugen.

    ich sehe da push_heap, pop_heap, make_heap, sort_heap. könnte reichen.

    Ich hab mir dafür eine priority_queue hergenommen und es funktioniert auch alles prima:
    Elemente einfügen, pushen und poppen...alles korrekt sortiert.
    Allerdings muß ich im Laufe meines Algos beliebige Elemente aus dem Heap updaten (d.h. deren Priorität kann sich ändern).

    dann ist ein heap nicht mehr die geeignete datenstruktur. wie kommste eigentlich an die elemete, die geupdatet werden sollen? läufste linear von vorn bis hinten durch? dann brauchste eh keinen heap. der heap ist nämlich da, um speed zu machen. sogar ein fitzelchen mehr als ein normaler binärbaum. wenn du den überstrapazierst, geht er aber in die eisen und macht dein prog lahm. das haen alle furchtbar schnellen so an sich.

    Und hier stößt die PQ auch schon an ihre Grenzen. Sie verfügt über keinerlei Updatefunktion, oder seh ich das falsch?

    dazu nimmst du es einfach raus, läßt das löch herkömmlich in O(log(n)) auffüllen, so, wie wenn du dort die wurzel entfernt hättest, stofst das elem in das neu enstandene loch auf der untersten ebene und läßt es in O(log(n)) ganz normal einsortieren.

    ka, ob eine fertige pq das hat.

    Gibt es einen anderen schönen Weg mit der STL eine Heapstruktur zu halten?

    es gibt einen schönen weg. aber ich kann dir nicht sagenb, ob der mit der stl irgendwie verträglich ist.



  • volkard schrieb:

    hä?
    warum das denn?

    5        5
        / \      / \
       3   4    4   3
    

    Beides sind gültige Heaps, da ein Heap nur definiert, dass unter jedem Knoten, die gleichen oder kleine Werte enthalten sind. Ihre Reihenfolge ist egal. Da die Priority-Queue automatisch sortiert, kann sie nur 5 4 3 erreichen. Ob das unvorteilhaft ist oder nicht, könnte ich so nicht sagen.



  • Harry Hirsch schrieb:

    volkard schrieb:

    hä?
    warum das denn?

    5        5
        / \      / \
       3   4    4   3
    

    Beides sind gültige Heaps, da ein Heap nur definiert, dass unter jedem Knoten, die gleichen oder kleine Werte enthalten sind. Ihre Reihenfolge ist egal. Da die Priority-Queue automatisch sortiert, kann sie nur 5 4 3 erreichen. Ob das unvorteilhaft ist oder nicht, könnte ich so nicht sagen.

    ich hab keinen schimmer, von was du redest.
    such dir ein argument raus, was dich widerlegt und widerlege dich.

    entweder ist der zugriff auf die sequenz nicht möglich...
    und dann ist deine behauptung nicht beobachtbares verhalten und jeder kann optimieren, wie er lustig ist.

    oder ist der zugriff nur lesend möglich...
    dann kann immernoch jeder optimieren, wie er lustig ist. zum bleistift push immer platt zu nem pus_back auf die sequenz weiterleiten, bois das erste top kommt und dann erst heapify machen.

    oder it der zugriff fei (ist bei mir so, naja protected). dann kann sogar heder die sequenz verfummeln.

    und das nur unter der wahnwitzigen voraussetzung, daß der ctor der pq als argument keine sequenz nehmen kann, die mit make_heap heapifiziert wird (was bekanntlich leicht schneller ist als alle reinzupushen).



  • Danke erstmal für die Tipps.

    So wie es aussieht ist es mit reiner STL-Programmierung scheinbar nicht möglich meinen Heap effizient zu implementieren. Dadurch, dass sich die Priorität meiner Elemente ändern kann, ist mit den pop_ push_ make und sort_heap nicht viel anzufangen. Ich müßte immer, nachdem ich eine Element geändert habe, den Heap neu erzeugen.
    Wahrscheinlich ist es besser, ich baue mir selbst einen Heap basierend auf einem vector, dann kann ich die STL-Funktionen wenigstens teilweise nutzen.

    volkard schrieb:

    wie kommste eigentlich an die elemete, die geupdatet werden sollen? läufste linear von vorn bis hinten durch? dann brauchste eh keinen heap. der heap ist nämlich da, um speed zu machen.

    In meinem Vektor schiebe ich nur Pointer hin und her, die ich extra nocheinmal in einem Feld speichere. So kann ich dann über die Punktkoordinaten auf das Element zugreifen. Wenn ich dann noch die Heapposition mitspeichere, finde ich das richtige element auch im Heap sehr schnell.

    Heiko



  • Hallo @all,

    Erstmal ein Lob fuer die grossartige Arbeit von allen Forumsteilnehmern, ihr habt mir schon oft durch die Beitraege bei gewissen Problemen geholfen. Ich steh aber momentan vor einem Problem das so noch nicht beantwortet wurde (ich habs zumindest nicht gefunden hier).

    Kennt sich jemand gut mit den Interna's der STL-Heap-Implementierung aus? Ich haette da naemlich einige Fragen deren Antworten sich bis jetzt ziemlich gut vor mir versteckt haben im Internet.

    1. Wie effizient ist diese Implementierung ueberhaupt gegenueber einer Eigenimplementierung? Ich hoere immer wieder das die STL schon (natuerlich richtig angewendet) ziemlich effizient sein soll und es da kaum Geschwindigkeitsvorteile gibt bei einer Eigenimplementierung in C++? (speziell bei vector + heap)

    2. Nehmen wir an ich haette einen 'vector' auf dem ein Heap aufgebaut werden soll, ungefaehr so:

    vector<obj*>* bvec;
    ...
    make_heap( bvec->begin(), bvec->end() );
    

    Natuerlich davon ausgehend die reingesteckten Objekte haben den Operator< implementiert fuer einen Vergleich. Was ist hier die effizienteste Methode den Heap z.b. bei einem Austausch eines Elements wiederherstellen zu lassen? In der STL ist so ein Vorgehen eigentlich nicht speziell definiert, hoechstens eine nochmalige Anwendung des make_heap()-Befehls, aber macht der wirklich dann nur noetige Schritte (durchsickern etc.) und nicht einen kompletten Neubau? (Hoert sich vielleicht verrueckt an, aber ich trau dem Ganzen nunmal net so ganz 🙂 )

    3. Meine letzte Frage ist bezueglich eines Artikels auf dieser Seite:
    http://www.infrasoft.co.at/hn/stl.htm (nur bis 1. ...)
    Sind seine Ausfuehrungen korrekt? Besonders interessant finde ich diesen Satz: "Weil der vector beim sortieren, herumschieben von Elementen in diversen anderen algorithmen (man denke an unique, make_heap, reverse und andere), und beim reallokieren die Elemente umkopieren muß". Ich bin kein Speicherfreak, aber bedeutet das, dass selbst wenn ich wie oben gezeigt nur Pointer auf die Objekte in den vector lege trotzdem grosser Kopieraufwand noetig wird beim sortieren a la make_heap? Kann auch sein das ich des falsch verstanden hab.

    Wie vielleicht deutlich wurde bin ich auf der Suche nach der effizientesten Loesung. Danke fuer alle die mir hierbei helfen koennen.

    greetings,

    Andreas



  • Schau dir mal das hier an:
    http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6110

    In den FrontPropagation - Files wird ein STL - Heap verwendet,
    der aus meiner Sicht auch sehr effizient ist.
    Allerdings ist das Thema evtl. mathematisch nicht so einfach zu verstehen,
    aber dir geht es ja nur um die Implementierung eines Heaps!

    Gruß,
    Cold



  • Muß meine Aussagen berichtigen,
    er benutzt in ner neuen Version wohl doch
    eine eigene Implementierung.
    Na ja, scheint ja noch schneller zu sein.
    Auf jeden Fall ist es sicher ne Hilfe.

    Cold



  • danke dafuer.

    koennte mir einer auch die sache mit den smart-pointern erklaeren ob die nun wirklich
    besser sind und warum die objekte kopiert werden muessen beim sortieren obwohl sich nur
    die pointer im vector befinden (zumindest laut der aussage des autors der angegebenen
    website)?

    thx



  • Ich beantworte jetzt meine ersten 2 Fragen jetzt selber falls jemand mal
    auf aehnliche Probleme stoesst 🙂

    zu 1.:

    Gut fuer die Diskussion ueber Vektoren sollte man im Forum am besten
    nach Themen im Stil "Array vs Vector" suchen, da wird recht ausfuehrlich
    auf die Effizienz eingegangen.

    Fuer die Heapeigenimplementierung hab ich eigentlich momententan keinen
    richtigen Grund gefunden, jedoch ist der "Numerical Recipes"-Algorithmus in
    dieser Hinsicht wahrscheinlich einer der effizientesten. Keine Ahnung wie er
    in der STL implementiert ist, aber es koennte auch auf etwas aehnliches
    rauslaufen.

    zu 2.:

    Nein, make_heap() baut den Heap immer neu auf und ist damit auf KEINEN
    Fall fuer ein reines Versickern zu empfehlen. Hier ist die Eigenimplementierung
    um das zig-fache schneller. (-> Numerical Recipes)
    Hat man erstmal das Versickern implementiert ist der Schritt zum
    vollstaendigen Algorithmus nicht weit und man sollte ueberlegen alles
    selber zu schreiben. (Nachtrag zu 1.)

    Cheers!


Anmelden zum Antworten