Heap und std::vector und das ganze auf Pointern

Max3000

Hallo Leute.

Ich hätte mal eine kurze Frage.
Will grad einen Graphen-Algo. implementieren bei dem ich einen Heap brauche.
Ich mache folgendes:

1. Einlesen der Knoten und speichern in einen std::vector, die Knotenklasse habe ich selber geschrieben.
2. Erzeugen eines neuen vectors, der dann mein heap sein soll
3. push, pop und so weiter sollen a la Dijkstra auf den Heap ausgeführt werden.

Mein Problem ist jetzt, dass ich für die Heap-Operationen den operator< brauche, damit die make_heap, pop_heap und push_heap entscheiden können, wenn ein Element größer ist als ein anderes. Wie mach ich das jetzt am besten?

std::vector<Vertex*> heap;

geht schonmal nicht, weil

operator<(const Vertex*,const Vertex*)

nicht gültig ist.
Also bleibt nur noch

std::vector<Vertex> heap;

Wenn ich jetzt

heap.push_back(myVertex)

aufrufe wird anscheinend ein neues Vertex-Objekt angelegt (Copy Construktor wird aufgerufen) und gespeichert.
Das würde theoretisch funktionieren, aber ich will nicht dass das Objekt kopiert wird.

Versteht ihr mein Problem?
Wie würdet ihr das machen?
Ich will ja eigentlich nur ein Paar Pointer auf Vertex in meinem heap und die sollen dann nur dort drin gehalten werden und NICHT Kopien von meinen Objekten.

Ich habe gelesen dass es für std::vector als 2. Templateparameter den Allocator gibt. Könnte der mir weiterhelfen? Habt ihr damit Erfahrung? Was kann man damit machen?

Schönen Gruß und danke schonmal

Max

volkard

also brauchst Du sowas wie den

struct TheMysticVertexComparator{
   bool operator()(Vertex const* a,Vertex const* b){
      return *a<*b;
   }
};

Max3000

Also Funktor meinst du?
Und wie kann ich den Heap-Operationen sagen dass die den zum Vergleichen der Elemente nehmen sollen?

Aber die Idee ist gut, danke schonmal.

volkard

Max3000 schrieb:

Also Funktor meinst du?
Und wie kann ich den Heap-Operationen sagen dass die den zum Vergleichen der Elemente nehmen sollen?

So ein Objekt anlegen und als Parameter übergeben.
http://www.cplusplus.com/reference/algorithm/make_heap/

Max3000

Du bist klasse.
Vielen Dank!

Willst Du Dir etwa eine priority queue bauen? Die gibt es nämlich schon in der Standardbibliothek: http://www.cplusplus.com/reference/stl/priority_queue/

Max3000

Eigentlich ja. Ich will Elemente einfügen können und will mir immer nur das kleinste Element wieder rausholen.
MIt der STL Priority Queue würde das sicherlich auch gehen. Danke für den Hinweis. Jetzt hab ich nur vector und die heap-algorithmen.
Könnte die priority_queue vielleicht schneller sein? Dann probier ich die auch noch aus.

Grüße

Max

Max3000

Oder ich glaube dass die Priority-Queue doch nicht geht.
In meinem Algorithmus brauche ich eine "decreaseKey"-Funktion.
Die soll den key-Wert eines Elements im Heap verkleinern und das Element dann entsprechend wieder ordnern, dass halt Heap-Order herrscht.

Mit priority_queue hab ich ja nur wenige Methoden. pop, push und top um auf Elemente zuzugreifen. Das geht mit Priority-Queue nicht wirklich, oder?

drakon

Max3000 schrieb:

Oder ich glaube dass die Priority-Queue doch nicht geht.
In meinem Algorithmus brauche ich eine "decreaseKey"-Funktion.
Die soll den key-Wert eines Elements im Heap verkleinern und das Element dann entsprechend wieder ordnern, dass halt Heap-Order herrscht.

Mit priority_queue hab ich ja nur wenige Methoden. pop, push und top um auf Elemente zuzugreifen. Das geht mit Priority-Queue nicht wirklich, oder?

Nein. Dafür brauchst du (wenn du es effizient haben willst) einen Fibonacci Heap, der die gewünschten Funktionen bereitstellt. Das Problem ist einfach, dass die STL keinen Fibonacci Heap anbietet.

Es gibt aber Alternativen (für MST sowie kürzeste Wege), welche ohne einen F-Heap auskommen, sind aber weniger effizient.

Max3000

genau den Dijkstra-Algo will ich mit FibonacciHeap und BinaryHeap (std::vector + make_heap, etc...) ausprobieren und vergleichen.
FibonacciHeap ist schon drin und der läuft. Und std::vector + heap-algorithmen mitlerweile auch, aber noch nicht richtig optimiert.

Wen's interessiert der Vergleich:
Für einen Graphen mit 63360 Knoten und 252432 Kanten brauchen:
FibonacciHeap: 129.4 ms
BinaryHeap: 462.9 ms

Allerdings suche ich bei der decreaseKey Methode, die der Dijkstra-Algo brauch für den binären Heap noch was effizientes. Da mach ich zur Zeit noch ein make_heap auf den kompletten vector.

volkard

Max3000 schrieb:

Allerdings suche ich bei der decreaseKey Methode, die der Dijkstra-Algo brauch für den binären Heap noch was effizientes. Da mach ich zur Zeit noch ein make_heap auf den kompletten vector.

decreaseKey? Ist es das, was ich mir drunter vorstelle, nämlich ein Element verkleinern und dabi vorrutschen lassen?
Einfach push_heap nehmen, oder? Die Heap-Bedingung, daß das geänderte Element kleinergleich wie seine Kinder ist, bleibt ja bestehen.

volkard

Max3000 schrieb:

Wen's interessiert der Vergleich:
Für einen Graphen mit 63360 Knoten und 252432 Kanten brauchen:
FibonacciHeap: 129.4 ms
BinaryHeap: 462.9 ms

Ja, will ich wissen. Also die nächste Version, wenn der Vergleich fair ist.

Max3000

Was meinst du mit fair?

Die decreaseKey Methode ist genau wie du beschreibst, dass der Key verkleinert wird und damit das Element im Heap aufsteigt. push_heap ist doch aber wenn das Element hinten hinzugefügt wird und dann nach oben gepusht wird oder?
Wie mach ich das genau?

Zur zeit hab ich:

headOfCurrentEdge->key = v->key + currentEdge->length; // decrease the key
make_heap(heap.begin(), heap.end(), comp); // order heap

Vielleicht gehts ja auch mit push_heap, wobei das zweite Argument ein pointer auf das zu verkleinernde Objekt im Heap ist, oder was sagt ihr?

drakon

volkard schrieb:

Max3000 schrieb:

Allerdings suche ich bei der decreaseKey Methode, die der Dijkstra-Algo brauch für den binären Heap noch was effizientes. Da mach ich zur Zeit noch ein make_heap auf den kompletten vector.

decreaseKey? Ist es das, was ich mir drunter vorstelle, nämlich ein Element verkleinern und dabi vorrutschen lassen?
Einfach push_heap nehmen, oder? Die Heap-Bedingung, daß das geänderte Element kleinergleich wie seine Kinder ist, bleibt ja bestehen.

Das Problem an push_heap ist denke ich, dass es nicht in konstanter Zeit läuft. Ein decrease_key in einem Fibonacci Heap hingegen ist (amortisiert) konstant.

decrease_key wird ja max. für jede Kante aufgerufen, was dann bei push_heap O(mlogn) ergibt also O(n^2 * logn). Ein F-Heap hat aber O(nlogn + m). Je nach Dichte des Graphen kann das, denke ich schon was ausmachen.

volkard

Max3000 schrieb:

Zur zeit hab ich:
headOfCurrentEdge->key = v->key + currentEdge->length; // decrease the key
make_heap(heap.begin(), heap.end(), comp); // order heap
Vielleicht gehts ja auch mit push_heap, wobei das zweite Argument ein pointer auf das zu verkleinernde Objekt im Heap ist, oder was sagt ihr?

Ja, das meine ich.

Max3000

Verdammt, jetzt hab ich make_heap durch push_heap ersetzt und jetzt ist mein FibonacciHeap den ich selber implementiert habe langsamer als der Binäre Heap.

Ich muss doch bei push_heap dann mit dem End-Pointer auf das Element setzen, was ich verkleinert hab oder?

push_heap(heap.begin(), elementToDecrease);

wie ich an den zweiten Pointer komme weiß ich leider auch noch nicht.
Der wird doch vom std::vector intern verwaltet oder?

life

drakon schrieb:

decrease_key wird ja max. für jede Kante aufgerufen, was dann bei push_heap O(mlogn) ergibt also O(n^2 * logn). Ein F-Heap hat aber O(nlogn + m). Je nach Dichte des Graphen kann das, denke ich schon was ausmachen.

Dijsktra Algorithmus mit binären Heap implementiert hat eine Laufzeit von O(n log n + m log n), wenn n die Anzahl der Knoten und m die Anzahl der Kanten ist.

drakon

life schrieb:

drakon schrieb:

decrease_key wird ja max. für jede Kante aufgerufen, was dann bei push_heap O(mlogn) ergibt also O(n^2 * logn). Ein F-Heap hat aber O(nlogn + m). Je nach Dichte des Graphen kann das, denke ich schon was ausmachen.

Dijsktra Algorithmus mit binären Heap implementiert hat eine Laufzeit von O(n log n + m log n), wenn n die Anzahl der Knoten und m die Anzahl der Kanten ist.

Ich habe nie von einem binärem Heap gesprochen. m wird ja n^2 bei dichten Grpahen (von dünnen müssen wir ja nicht sprechen, da beides sehr effizient ist). Dann hast du mit deiner Laufzeit (wenn die stimmt) O(n^2 * logn), während mit dem F-Heap hast du lediglich O(n^2 + nlogn) = O(n^2).

@Max3000:
Du musst das Element, dass du einfügen willst mit push_back in den vector einfügen und dann push_heap aufrufen, welcher dann den letzten Wert korrekt in den Heap eingliedert (er wird in O(logn) versickert).

life

Bei der einen Laufzeitangabe |E|=|V|^2 vorauszusetzen und bei der anderen nicht, ist jedenfalls nicht ganz fair.

Ob |E|=|V|^2 der typische Fall ist, hängt dann wohl von deiner Anwendung ab. Normalerweise würde ich aber erwarten, dass die Implementierung mittels binären Heap effizienter ist als eine Implementierung mit fib Heap. Fib. heaps sind nämlich ihmo eher nur von theoretischen Interesse ;).

Ergänzung zu @Max3000: Also z.B. push_heap(&heap[0], (&elementToDecrease)+1);

Max3000

@ drakon:
Beim Einfügen in den Heap hab ich das so gemacht. Aber ich will ja ein Element verkleinern, was schon im Heap drin ist.

Also mein einfügen sieht so aus:

heap.push_back(headOfCurrentEdge);
push_heap(heap.begin(), heap.end(), comp);

und mein decreaseKey jetzt so:

headOfCurrentEdge->key = v->key + currentEdge->length;
push_heap(heap.begin(), heap.end(), comp);

wobei ich denke dass es nicht mal nötig ist bei heap.end() anzufangen. Man kann sicherlich auch ab der stelle pushen, wo headOfCurrentEdge liegt, aber an die komm ich leider nicht. Zumindest weiß ich noch nicht wie.

Wo wir grad beim FibonacciHeap sind, ich hab rausgefunden was meinen so ausbremst. Beim deleteMin muss man ja das minimale Element löschen und alle Kinder in die root Liste einfügen und dann verlinken, wenn 2 Elemente den selben Rang haben.
Dazu fügt man einfach alle Elemente in einen Liste an die x-te Stelle, wobei x der Rang ist. Ist da schon eins wird gelinkt, ansonsten nur eingefügt.
Zur zeit habe ich ein Array aus 100 Elementen (bitte verspottet mich jetzt nicht) und resette das vor jedem deleteMin. Welche Datenstruktur ist dafür am besten geeignet?
-std::vector ist mist, weil es sein kann dass ich erst rootList[5], dann rootList[2] u.s.w. zum Beispiel schreiben will.
-std::map sieht ganz gut aus aber damit hab ich mich noch nicht näher befasst.

Irgendwelche Empfehlungen?

Grüße

Max