Gibt es einen stabilen Haufen?

Gibt es eine Prioritätswarteschlangendatenstruktur, die die folgenden Vorgänge unterstützt?

• Einfügen (x, p) : Fügt einen neuen Datensatz x mit der Priorität p hinzu
• StableExtractMin () : Gibt den Datensatz mit minimaler Priorität zurück und löscht ihn. Dabei werden die Bindungen nach Einfügereihenfolge getrennt .

Daher würde nach Einfügen (a, 1), Einfügen (b, 2), Einfügen (c, 1), Einfügen (d, 2) eine Sequenz von StableExtractMin's a, dann c, dann b, dann d zurückgeben.

Offensichtlich könnte man verwenden irgendeine Prioritätswarteschlange Datenstruktur , die durch das Paar Speichern $(p, time)$ wie die tatsächliche Priorität, aber ich in Datenstrukturen daran interessiert , dass sie nicht explizit speichern die Einführungszeiten (oder Insertion Reihenfolge), in Analogie zu einer stabilen Sortierung.

Äquivalent (?): Gibt es eine stabile Version von Heapsort, die keinen zusätzlichen Platz für $\Omega(n)$ ?

Die Bently-Saxe-Methode ergibt eine recht natürliche Warteschlange mit stabiler Priorität.

Speichern Sie Ihre Daten in einer Folge von sortierten Arrays . A Ich habe Größe 2 Ich . Jedes Array unterhält auch einen Zähler c i . Die Array-Einträge A i [ c i ] , ... , A i [ 2 i - 1 ] enthalten Daten.$A_0,\ldots,A_k$$A_i$$2^i$$c_i$$A_i[c_i],\ldots,A_i[2^i-1]$

Für jedes wurden alle Elemente in A i in jüngerer Zeit als die in A i + 1 hinzugefügt, und in jedem A i -Element wird die Reihenfolge nach dem Wert geordnet, wobei Bindungen durch Platzieren älterer Elemente vor neueren Elementen aufgehoben werden. Beachten Sie, dass dies bedeutet, dass wir A i und A i + 1 zusammenführen und diese Reihenfolge beibehalten können. (Im Falle von Bindungen während der Zusammenführung nehmen Sie das Element von A i + 1. )$i$$A_i$$A_{i+1}$$A_i$$A_i$$A_{i+1}$$A_{i+1}$

Um einen Wert einzufügen , suchen Sie das kleinste i , sodass A i 0 Elemente enthält, führen Sie A 0 , … , A i - 1 und x zusammen , speichern Sie dies in A i und setzen Sie c 0 , … , c i entsprechend.$x$$i$$A_i$$A_0,\ldots,A_{i-1}$$x$$A_i$$c_0,\ldots,c_i$

Um die min zu extrahieren, finde den größten Index so, dass das erste Element in A i [ c i ] über alle i minimal ist und c i inkrementiert .$i$$A_i[c_i]$$i$$c_i$

Nach dem Standardargument ergibt dies eine amortisierte -Zeit pro Operation und ist aufgrund der oben beschriebenen Reihenfolge stabil.$O(\log n)$

Für eine Folge von Einfügungen und Auszügen werden n Array-Einträge (keine leeren Arrays) plus O ( log n ) Wörter mit Buchhaltungsdaten verwendet. Es beantwortet nicht Mihais Version der Frage, aber es zeigt, dass die stabile Einschränkung nicht viel Platz in Anspruch nimmt. Insbesondere zeigt es, dass es keine Untergrenze von Ω ( n ) für den zusätzlichen Raum gibt, der benötigt wird.$n$$n$$O(\log n)$$\Omega(n)$

Update: Rolf Fagerberg weist darauf hin, dass diese gesamte Datenstruktur in ein Array der Größe gepackt werden kann , wobei n die Anzahl der bisherigen Einfügungen ist , wenn wir Nullwerte (Nicht-Datenwerte) speichern können .$n$$n$

Beachten Sie zunächst, dass wir in dieser Reihenfolge in ein Array packen können (mit A k zuerst, gefolgt von A k - 1, wenn es nicht leer ist, und so weiter). Die Struktur davon wird vollständig durch die Binärdarstellung von n , der Anzahl der bisher eingefügten Elemente, codiert . Wenn die Binärdarstellung von n eine 1 an der Position hat i , dann A i wird besetzen 2 i Matrixort, sonst wird es keine Feldpositionen besetzen.$A_k,\ldots,A_0$$A_k$$A_{k-1}$$n$$n$$i$$A_i$$2^i$

Wenn Sie einfügen und die Länge unseres Arrays um 1 erhöhen, können Sie A 0 , … , A i und das neue Element mithilfe vorhandener stabiler Zusammenführungsalgorithmen zusammenführen.$n$$A_0,\ldots,A_i$

Wo wir nun Nullwerte verwenden, müssen wir die Zähler loswerden . In A i speichern wir den ersten Wert, gefolgt von c i -Null-Werten, gefolgt von den verbleibenden 2 i - c i - 1- Werten. Während einer Extraktionsminute können wir den zu extrahierenden Wert in O ( log n ) -Zeit finden, indem wir A 0 [ 0 ] , … , A k [ 0 ] untersuchen . Wenn wir diesen Wert in A i [ $c_i$$A_i$$c_i$$2^i-c_i-1$$O(\log n)$$A_0[0],\ldots,A_k[0]$ wir A i [ 0 ] auf null und führen dann eine binäre Suche auf A i durch , um den ersten Nicht-Null-Wert A i [ c i ] zu finden und A i [ 0 ] und A i [ c i ] zu tauschen.$A_i[0]$$A_i[0]$$A_i$$A_i[c_i]$$A_i[0]$$A_i[c_i]$

Das Endergebnis: Die gesamte Struktur kann mit einem Array implementiert werden, dessen Länge mit jeder Einfügung erhöht wird, und einem Zähler , der die Anzahl der Einfügungen zählt.$n$

Ich bin mir nicht sicher, welche Einschränkungen Sie haben. qualifiziert sich das Folgende? Speichern Sie die Daten in einem Array, das wir als impliziten Binärbaum interpretieren (wie einen Binärhaufen), wobei sich die Datenelemente jedoch auf der untersten Ebene des Baums und nicht auf den internen Knoten befinden. Jeder interne Knoten des Baums speichert den kleineren der Werte, die von den beiden untergeordneten Knoten kopiert wurden. Kopieren Sie bei Unentschieden das linke Kind.

Um das Minimum zu finden, schauen Sie auf die Wurzel des Baumes.

Wenn Sie ein Element löschen möchten, markieren Sie es als gelöscht (verzögertes Löschen) und verschieben Sie den Baum nach oben (jeder Knoten auf dem Pfad zum Stammverzeichnis, der eine Kopie des gelöschten Elements enthielt, sollte durch eine Kopie seines anderen untergeordneten Elements ersetzt werden). Behalten Sie die Anzahl der gelöschten Elemente bei, und erstellen Sie die Struktur neu, falls sie jemals zu groß werden sollte, wobei die Reihenfolge der Elemente auf der untersten Ebene beibehalten wird. Die Neuerstellung dauert linear, sodass dieser Teil nur die konstante amortisierte Zeit zur Zeit hinzufügt Komplexität der Bedienung.

Um ein Element einzufügen, fügen Sie es an der nächsten freien Position in der unteren Reihe des Baums hinzu und aktualisieren Sie den Pfad zum Stamm. Wenn die unterste Zeile voll wird, verdoppeln Sie die Größe des Baums (ebenfalls mit einem Amortisationsargument; beachten Sie, dass sich dieser Teil nicht von der Notwendigkeit unterscheidet, neu zu erstellen, wenn ein Standard-Binärheap aus seinem Array herauswächst).

Es ist jedoch keine Antwort auf Mihais strengere Version der Frage, da sie doppelt so viel Speicher benötigt wie eine echte implizite Datenstruktur, auch wenn wir die Platzkosten für die langsame Behandlung von Löschvorgängen ignorieren.

Ist das Folgende eine gültige Interpretation Ihres Problems:

Sie müssen N Schlüssel in einem Array von A [1..N] ohne Zusatzinformationen speichern, damit Sie Folgendes unterstützen können: * Schlüssel einfügen * Min. Löschen, wodurch das früheste eingefügte Element ausgewählt wird, wenn es mehrere Minima gibt

Dies scheint ziemlich schwierig zu sein, da die meisten impliziten Datenstrukturen den Trick spielen, Bits in der lokalen Reihenfolge einiger Elemente zu codieren. Wenn mehrere Spieler gleich sind, muss ihre Reihenfolge beibehalten werden, sodass solche Tricks nicht möglich sind.

Interessant.

Kurze Antwort: Das kannst du nicht.

Etwas längere Antwort:

Sie benötigen zusätzlichen Speicherplatz, um das "Alter" Ihres Eintrags zu speichern, wodurch Sie zwischen identischen Prioritäten unterscheiden können. Außerdem benötigen Sie Ω ( n ) Platz für Informationen, die ein schnelles Einfügen und Abrufen ermöglichen. Plus Ihre Nutzlast (Wert und Priorität).$\Omega(n)$$\Omega(n)$

Und für jede Nutzlast Sie speichern, werden Sie in der Adresse zu "verstecken" einige Informationen können (zB bedeutet Y ist älter als X). Aber in diesen "versteckten" Informationen werden Sie entweder das "Alter" oder die "Schnellabruf" -Informationen verbergen. Nicht beide.$addr(X) < addr(Y)$

Sehr lange Antwort mit ungenauer Flockenpseudomathematik:

Hinweis: Wie bereits erwähnt, ist das Ende des zweiten Teils skizzenhaft. Wenn irgendein Mathematiker eine bessere Version liefern könnte, wäre ich dankbar.

Lassen Sie uns über die Datenmenge nachdenken, die auf einer X-Bit-Maschine (z. B. 32 oder 64 Bit) mit Maschinenwörtern für Datensätze (Wert und Priorität) vorhanden ist .$P$

Sie haben eine Reihe potenzieller Datensätze, die teilweise sortiert sind: und ( a , 1 ) = ( a , 1 ), aber Sie können ( a , 1 ) und ( b , 1 ) .$(a,1) < (a,2)$$(a,1) = (a,1)$$(a,1)$$(b,1)$

Sie möchten jedoch in der Lage sein, zwei nicht vergleichbare Werte aus Ihrer Datensatzgruppe zu vergleichen, basierend auf dem Zeitpunkt, zu dem sie eingefügt wurden. Sie haben hier also einen anderen Satz von Werten: die, die eingefügt wurden, und Sie möchten ihn mit einer Teilreihenfolge erweitern: wenn X vor Y eingefügt wurde .$X < Y$$X$$Y$

Im schlimmsten Fall wird Ihr Speicher mit Datensätzen des Formulars gefüllt (mit jeweils unterschiedlichen ? ). Sie müssen sich also vollständig auf die Einfügezeit verlassen, um zu entscheiden, welche verwendet wird zuerst raus.$(?,1)$$?$

• Die Einfügungszeit (relativ zu anderen Aufzeichnungen noch in der Struktur) erfordert Bits von Informationen (mit P-Byte - Nutzlast und 2 X zugänglich Bytes des Speichers).$X - log_2(P)$$2^X$
• Die Nutzlast (der Wert und die Priorität Ihres Datensatzes) erfordert Maschineninformationswörter.$P$

Das bedeutet , dass Sie müssen irgendwie speichern zusätzliche Bits an Informationen für jeden Datensatz zu speichern. Und das ist O ( n ) für n Datensätze.$X - log_2(P)$$O(n)$$n$

Wie viel Information liefert uns nun jede "Speicherzelle"?

• Datenbits ( W ist die Maschinenwortbreite).$W$$W$
• Adressbits.$X$

Nehmen wir nun an, dass (Nutzlast ist mindestens ein Maschinenwort breit (normalerweise ein Oktett)). Dies bedeutet, dass X - l o g 2 ( P ) < X ist , sodass wir die Informationen zur Einfügungsreihenfolge in die Adresse der Zelle einfügen können. Das ist, was in einem Stapel passiert: Zellen mit der niedrigsten Adresse betraten zuerst den Stapel (und werden als letztes herauskommen).$P \geq 1$$X - log_2(P) < X$

Um alle unsere Informationen zu speichern, haben wir zwei Möglichkeiten:

• Speichern Sie die Einfügungsreihenfolge in der Adresse und die Nutzdaten im Speicher.
• Speichern Sie beide im Speicher und lassen Sie die Adresse für eine andere Verwendung frei.

Um Verschwendung zu vermeiden, verwenden wir natürlich die erste Lösung.

Nun zu den Operationen. Ich nehme an, Sie möchten haben:

• mit O ( l o g n ) Zeitkomplexität.$Insert(task, priority)$$O(log n)$
• $StableExtractMin()$$O(log n)$

$StableExtractMin()$

Der wirklich wirklich allgemeine Algorithmus sieht so aus:

1. $O(log n)$
2. $O(log n)$
3. Gib es zurück.

$0(1)$$O(1)$$O(1)$

$O(log n)$$2^(X - log_2(P))$

$X - log_2(P)$$O(log n)$$O(log n)$

$O(log n)$

$O(log n)$$X - log_2(P)$

$O(log n)$

$X - log_2(P)$$O(log n)$

Der Einfügealgorithmus muss in der Regel nur einen Teil dieser Informationen aktualisieren. Ich denke nicht, dass es mehr kostet (in Bezug auf den Speicher), wenn die Leistung schnell ist.

$X - log_2(P)$

• $X - log_2(P)$
• $P$
• $X - log_2(P)$

$\Omega(n)$

Wenn Sie Ihre Prioritätswarteschlange als ausgeglichenen Binärbaum implementieren (eine beliebte Option), müssen Sie nur sicherstellen, dass beim Hinzufügen eines Elements zum Baum dieses links von Elementen mit gleicher Priorität eingefügt wird.
Auf diese Weise wird die Einfügereihenfolge in der Struktur des Baums selbst codiert.

Ich denke nicht, dass das möglich ist

konkreter Fall:

       x
    x    x
  x  x  1  x
1  x  

min Haufen mit allen x> 1

Häufen wird irgendwann eine solche Wahl geben

       x
    1    1
  x  x  x  x
x  x  

Nun, welche 1 soll an root weitergegeben werden?