Ich habe eine Prioritätswarteschlange von Ereignissen, aber manchmal ändern sich die Ereignisprioritäten, daher möchte ich Iteratoren von den Ereignisrequestern in dem Heap beibehalten. Wenn sich die Priorität ändert, möchte ich, dass der Heap in log (n) Zeit angepasst wird. Ich werde immer genau einen Iterator haben, der auf jedes Element im Heap zeigt.Gibt es eine Heap-Klasse in C++, die das Ändern der Priorität von Elementen außer dem Kopf unterstützt?
Ich bin glücklich, dass die Erhöhung zu berichten hat jetzt einen Boost.Heap library mit etwas stellar data structures hinzugefügt.
Der Vorteil davon ist, dass Fibonacci-Heaps die Änderung der Priorität in konstanter amortisierter Zeit unterstützen.
Leider sind alle veränderbaren Heaps knotenbasiert (mit anderen Worten, sie haben eine zusätzliche Indirektion, wie von @wilx vorgeschlagen). @ Feruccios Antwort auf Boosts "veränderbare Haufen" hat einen Code, der es einem erlaubt, vektorbasierte mutierbare Haufen zu schreiben, wenn Sie bereit sind, Zeiger auf Handles zu haben, die in Ihrem Werttyp enthalten sind.
Das klingt nach mehr Indirektion. Speichern Sie stattdessen den Zeiger auf die Ereignisse in der Prioritätswarteschlange. Wenn sich die Priorität einiger Elemente der Warteschlange ändert, entfernen Sie sie und fügen Sie sie erneut ein.
Werfen Sie einen Blick auf Boost mutable heaps.
hier eine Warnung ist, dass Sie mit instabilen Ereignisse am Ende Sortierung, dh Reihenfolge der Ereignisse mit der gleichen Priorität nicht definiert ist (lese ‚wird sie neu geordnet werden.‘)
Sie können ein beliebiges Element in log (n) Zeit aus einem Heap entfernen. –
Ja, du hast Recht, dachte über etwas anderes :) –
kein Problem :) –
Danke, wenn ich am Ende selbst rollen muss, benutze ich das Schnipsel zum Starten. –
endete mit dieser Lösung –
@Ferruccio Danke, speicherte meine guten 45 Minuten und einige Bugs. –