Ich verwende eine Prioritätswarteschlange, die anfänglich die Priorität ihrer Elemente auf einer Heuristik basiert. Wenn Elemente aus der Warteschlange genommen werden, wird die Heuristik aktualisiert, und die Elemente, die sich derzeit in der Warteschlange befinden, können ihre Schlüssel erhöhen.
Ich weiß, dass es Heaps gibt (speziell Fibonacci-Heaps), die O (1) abgeschwächte Schlüsseloperationen amortisiert haben, aber gibt es irgendwelche Heap-Strukturen, die ähnliche Grenzen bei den Schlüsseloperationen haben?
Für meine Anwendung ist das weit von einem Leistungsproblem entfernt (ein binärer Haufen funktioniert gut), es geht nur um akademische Neugier.
Bearbeiten: Um zu verdeutlichen, suche ich nach einer Datenstruktur, die eine schnellere Zeit als O (logn) für die Schlüsselerhöhung Operation hat, Schlüssel nicht verringern. Meine Anwendung verringert niemals den Schlüssel, da die Heuristik die Priorität überschätzt.
Binäre Haufen sind zu unflexibel, um die logarithmische Komplexität zu übertreffen. Binomial-Heaps ermöglichen nur eine effizientere Join-Operation.
Andere Heaps mit einer guten Leistung bei der Verringerung der Schlüssel sind Paarungshaufen und 2-3 Haufen
Tatsächlich ist bei Fibonacci-Heaps die Operation zum Erhöhen der Schlüssel die gleiche wie die Taste zum Verringern. IMHO, es ist nur eine Tradition, die Operation "Taste verringern" zu nennen, weil es in einigen Algorithmen verwendet wird. Aber die Fibonacci-Heap-Implementierung erlaubt beides.
Tags und Links performance heap complexity-theory priority-queue