Ein Min-Heap mit besser als O (logn) erhöhen Schlüssel?

Question

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öht haben.

Ich weiß, es gibt Haufen (Fibonacci Heaps speziell), die amortisiert haben O (1) verringern Tastenoperationen, aber gibt es irgendwelche Heap-Strukturen, die ähnliche Grenzen auf die Erhöhung der Tastenoperationen haben?

Für meine Anwendung ist dies weit von einem Leistungsproblem (ein binärer Haufen funktioniert gut), es ist wirklich nur akademische Neugier.

Edit: um zu klären, ich bin auf der Suche nach einer Datenstruktur, die eine schnellere als O (logn) Zeit für die Erhöhung Taste Betrieb hat, nicht Schlüssel zu verringern. Meine Anwendung verringert niemals den Schlüssel, da die Heuristik die Priorität überschätzt.

Answer 1

Binäre Haufen sind zu unflexibel, um die logarithmische Komplexität zu übertreffen. Binomialhaufen ermöglichen nur eine effizientere Join-Operation.

Andere Haufen mit guten Abnahme-Key-Performance sind pairing heaps und 2-3 heaps

Answer 2

Binomial Heaps nehmen o (log n) Zeit für Abnahme Schlüsseloperationen! Ist das nicht langsamer als Fibonacci-Haufen?

Answer 3

Tatsächlich, mit Fibonacci-Heaps, ist die Erhöhung der Tastenbelegung die gleiche wie die Abnahmetaste. IMHO, es ist nur eine Tradition, die Operation "Taste verringern" zu nennen, weil es in einigen Algorithmen verwendet wird. Aber die Fibonacci-Heap-Implementierung ermöglicht beides.