Viele schnelle Prioritätswarteschlangen (wie der Fibonacci-Heap und Pairing-Heap ) unterstützt eine" sineze-key "-Operation, die ein bereits in der Prioritätswarteschlange gespeichertes Element übernimmt und dessen Priorität effizient verringert. Im Fall von Fibonacci und Pairing-Heap kann der sink-Schlüssel schneller ausgeführt werden, als wenn das Element aus der Prioritätswarteschlange entfernt und später erneut eingefügt wird.
Ich frage mich, ob eine ähnliche Operation auf geordneten Dictionary-Strukturen (binäre Suchbäume, Skip-Listen usw.) unterstützt werden kann. Nehmen wir an, ich habe ein geordnetes Wörterbuch und möchte den Schlüssel eines Schlüssel / Wert-Paares als einen anderen Schlüssel ändern. Ist es möglich, dies in der Zeit O (1) oder O (log log n) auf einer beliebigen Standarddarstellung eines geordneten Wörterbuchs zu tun? Ich bin neugierig, denn mit einer ausgeglichenen BST kann dies in O (log n) -Zeit gemacht werden, indem das Element entfernt und neu eingefügt wird, aber es scheint, als könnte es einen schnelleren Weg dafür geben.
Danke!
Stellen Sie sich das folgende Szenario vor:
Sie starten N Elemente. Jetzt,
In den meisten Implementierungen geordneter Wörterbücher würden die Schritte 1 und 3 beide eine O (N) -Zeit benötigen. Wenn die Verkleinerungs-Taste die Zeit O (1) oder O (Protokoll Log N) annimmt, dann nimmt Schritt 2 die Zeit O (N) oder O (N Protokoll Log N) an. Das bedeutet, dass Sie in O (N) oder O (N log log N) Zeit sortieren können.
Durch die untere Schranke von O (N log N) bei der vergleichsbasierten Sortierung bedeutet dies, dass Sie KEINEN Verkleinerungsschlüssel in O (1) oder O (N log log N) Zeit eingeben können, es sei denn
Ein sortiertes Array oder eine sortierte verknüpfte Liste unterstützt O(1) sink- oder enlarge-key (unter der Annahme, dass keine / minimale Duplikate vorhanden sind, siehe 4. Absatz). Dies liegt daran, dass Sie, wenn Sie darüber nachdenken, höchstens zwei Elemente für die Funktion zum Verringern oder Erhöhen der Schlüssel austauschen müssen.
Nicht die besten Datenstrukturen in der Praxis (obwohl sie ihren Platz haben), aber immer noch eine Antwort.
Die einzige Einschränkung ist, dass Sie einen Zeiger auf den Knoten benötigen, um damit zu beginnen, denn es wird bereits O(log n) und O(n) benötigen, nur um den Knoten zu finden.
Wenn es Duplikate gibt, kann eine Bewegung den schlimmsten Fall O(n) für beide annehmen (wenn die meisten Werte gleich sind), was ziemlich schlecht ist. Bei einer verknüpften Liste sollte es jedoch möglich sein, O(1) zu erhalten, indem Sie eine Art verknüpfte Liste von verknüpften Listen verwenden, wobei jeder Knoten in der großen verknüpften Liste einen bestimmten Wert und jede verknüpfte Liste von dort repräsentiert repräsentiert alle Knoten, die diesem Wert entsprechen.
(nicht gelöscht, weil es eine Schande zu sein scheint, zu verschwenden)
Worst-Case kleiner als O(log n) für das Verschieben um ein einzelnes Element ist für eine BBST- oder Skip-Liste nicht möglich, obwohl es mindestens so effizient ist wie ein erneutes Einfügen von was ich sagen kann. Der durchschnittliche Fall ist wahrscheinlich kleiner als O(log n) .
Wir suchen danach - Die Suche nach der Position des Elements, das Sie verschieben möchten, ist O(log n) und das müssen Sie natürlich tun.
Wenn Sie die Position schon aus irgendeinem seltsamen Grund haben:
Warum die Verschiebung im schlimmsten Fall nicht kleiner als O(log n) in einer BST sein darf: Berücksichtigen Sie, wenn Sie versuchen, die Wurzel zu verschieben, und das nächste Element auf der Höhe des Baums ist (z. B. das rechte Kind) ein linkes Kind mit einem linken Kind mit einem linken Kind mit einem linken Kind ... bis zur Höhe des Baumes). Sie benötigen O(log n) , um es zu finden.
Warum die Worst-Case-Verschiebung nicht kleiner als O(log n) in einer Überspringungsliste sein darf: Betrachten Sie ein Element in O(log n) lists, gefolgt von einem Element in O(log n) . dieser Listen (wenn dies möglich ist, scheint es so von das Bild zu sein, mein Verständnis von Skip-Listen ist etwas grundlegend) . Sie müssen die entsprechenden Artikel natürlich in O(log n) lists tauschen.
Wenn Sie bereits die Position haben, kann es eine effiziente geordnete Struktur geben, für die es möglich ist, aber wahrscheinlich nicht für irgendeine baumbasierte Struktur (wegen des oben dargelegten Arguments), die meines Wissens die Mehrheit sind von effizienten geordneten Strukturen.
Tags und Links algorithm data-structures decrease-key