Binomialhaufen – Enzyklopädie

In der Informatik ist ein Binomial-Heap ein Heap, der einem Binär-Heap ähnelt, aber auch das schnelle Zusammenführen von zwei Heaps unterstützt. Dies wird durch eine spezielle Baumstruktur erreicht. Es ist wichtig als Implementierung des abstrakten Datentyps für zusammenführbaren Heap (auch als zusammenführbarer Heap bezeichnet), der eine Prioritätswarteschlange ist, die die Zusammenführung unterstützt. Binomialhaufen wurden 1978 von J. Vuillemin [1] erfunden.

Binomial-Heap Bearbeiten

Ein Binomial-Heap wird als eine Menge von Binomial-Bäumen implementiert (vergleiche mit einem binären Heap mit der Form eines single binary tree), die rekursiv wie folgt definiert sind:

  • Ein Binomialbaum der Ordnung 0 ist ein einzelner Knoten
  • Ein Binomialbaum der Ordnung k hat einen Wurzelknoten, dessen Kinder Wurzeln von Binomialbäumen der Ordnung k −1 sind , k −2, …, 2, 1, 0 (in dieser Reihenfolge).

Binomialbäume der Ordnung 0 bis 3: Jeder Baum hat einen Wurzelknoten mit Teilbäumen aller Binomialbäume niedrigerer Ordnung Bäume, die hervorgehoben wurden. Beispielsweise ist der Binomialbaum der Ordnung 3 mit einem Binomialbaum der Ordnung 2, 1 und 0 (jeweils hervorgehoben als Blau, Grün und Rot) verbunden.

Ein Binomialbaum der Ordnung k hat 2 k Knoten, Höhe k .

Aufgrund seiner einzigartigen Struktur kann ein Binomialbaum der Ordnung k aus zwei Bäumen der Ordnung k −1 trivial konstruiert werden, indem einer von ihnen als das am weitesten links stehende Kind der Wurzel des anderen Baumes. Dieses Merkmal ist von zentraler Bedeutung für den Zusammenführungsvorgang eines Binomialhaufens, was sein Hauptvorteil gegenüber anderen herkömmlichen Haufen ist.

Der Name stammt von der Form: ein Binomialbaum der Ordnung

n { displaystyle n}

hat

( n d ) { displaystyle { tbinom {n} {d}}

Knoten in der Tiefe

d { displaystyle d}

Binomialkoeffizient.)

Struktur eines Binomial-Heaps

Ein Binomial-Heap wird als eine Gruppe von Binomial-Bäumen implementiert, die die Binomial-Heap-Eigenschaften erfüllen :

  • Jeder Binomialbaum in einem Heap gehorcht der Minimum-Heap-Eigenschaft : Der Schlüssel eines Knotens ist größer oder gleich dem Schlüssel seines übergeordneten Knotens.
  • Es kann nur einen der folgenden Werte geben: eins oder null Binomialbäume für jede Reihenfolge, einschließlich nullter Ordnung.

Die erste Eigenschaft stellt sicher, dass die Wurzel jedes Binomialbaums den kleinsten Schlüssel im Baum enthält, der für den gesamten Heap gilt .

Die zweite Eigenschaft impliziert, dass ein Binomialhaufen mit n Knoten aus höchstens 1 + log 2 n Binomialbäumen besteht. Tatsächlich werden die Anzahl und die Reihenfolge dieser Bäume eindeutig durch die Anzahl der Knoten bestimmt n : Jeder Binomialbaum entspricht den 1 Bits in der binären Darstellung der Zahl n . Zum Beispiel ist die Zahl 13 1101 in binär,

2 3 + 2 2 + 2 0 { displaystyle 2 ^ {3} + 2 ^ {2} + 2 ^ {0}}

und somit besteht ein Binomialheap mit 13 Knoten aus drei Binomialbäumen von Ordnungen 3, 2 und 0 (siehe Abbildung unten).

 Beispiel eines Binomial-Heaps "src =" http://upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/325px-Binomial-heap-13.svg. png "decoding =" async "width =" 325 "height =" 217 "srcset =" // upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/488px-Binomial- heap-13.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/650px-Binomial-heap-13.svg.png 2x "Daten -file-width = "498" data-file-height = "333
Beispiel für einen Binomial-Heap mit 13 Knoten mit unterschiedlichen Schlüsseln.
Der Heap besteht aus drei Binomial-Bäumen mit den Ordnungen 0, 2 und 3.

Implementierung [ Bearbeiten ]

Da für keine Operation ein wahlfreier Zugriff auf die Wurzelknoten der Binomialbäume erforderlich ist, können die Wurzeln der Binomialbäume in einer verknüpften Liste nach gespeichert werden aufsteigende Ordnung des Baumes.

Zusammenführen [ Bearbeiten ]

Um zwei Binomialbäume derselben Reihenfolge zusammenzuführen, vergleichen Sie zuerst den Stammschlüssel. Seit 7> 3 wird der schwarze Baum links (mit Wurzelknoten 7) als Teilbaum an den grauen Baum rechts (mit Wurzelknoten 3) angehängt. Das Ergebnis ist ein Baum der Ordnung 3.

Wie oben erwähnt, ist die einfachste und wichtigste Operation das Zusammenführen von zwei Binomialbäumen derselben Ordnung in einem Binomialhaufen. Aufgrund der Struktur von Binomialbäumen können sie trivial zusammengeführt werden. Da der Stammknoten das kleinste Element in der Struktur ist, ist der kleinere der beiden Schlüssel der Mindestschlüssel und wird zum neuen Stammknoten. Dann wird der andere Baum ein Teilbaum des kombinierten Baums. Diese Operation ist grundlegend für das vollständige Zusammenführen von zwei Binomialheaps.

 function  mergeTree (p, q)
     if  p.root.key <= q.root.key
         return  p.addSubTree (q)
     else 
         return  q.addSubTree (p)

Dies zeigt die Fusion zweier Binomialhaufen. Dies wird erreicht, indem zwei Binomialbäume derselben Ordnung nacheinander zusammengeführt werden. Wenn der resultierende zusammengeführte Baum die gleiche Reihenfolge wie ein Binomialbaum in einem der beiden Haufen hat, werden diese beiden erneut zusammengeführt.

Das Zusammenführen zweier Haufen ist möglicherweise das interessanteste und kann das interessanteste sein wird in den meisten anderen Vorgängen als Unterprogramm verwendet. Die Root-Listen beider Heaps werden auf ähnliche Weise wie beim Merge-Algorithmus gleichzeitig durchlaufen.

Wenn nur einer der Haufen einen Ordnungsbaum enthält j wird dieser Baum auf den zusammengeführten Haufen verschoben. Wenn beide Heaps einen Baum der Ordnung j enthalten, werden die beiden Bäume zu einem Baum der Ordnung j +1 zusammengeführt, so dass die Minimum-Heap-Eigenschaft erfüllt ist. Beachten Sie, dass es später möglicherweise erforderlich sein kann, diesen Baum mit einem anderen Baum der Ordnung j +1 zusammenzuführen, der in einem der Haufen vorhanden ist. Im Verlauf des Algorithmus müssen höchstens drei Bäume in beliebiger Reihenfolge untersucht werden (zwei aus den beiden Haufen, die wir zusammenführen, und einer aus zwei kleineren Bäumen).

Da jeder Binomialbaum in einem Binomialheap einem Bit in der Binärdarstellung seiner Größe entspricht, besteht eine Analogie zwischen dem Zusammenführen von zwei Heaps und dem binären Addieren der Größen der beiden Heaps , von rechts nach links. Wenn während der Addition ein Übertrag auftritt, entspricht dies einer Zusammenführung von zwei Binomialbäumen während der Zusammenführung.

Jeder Baum hat höchstens log n und daher ist die Laufzeit O (log n ).

 Funktion  Zusammenführen (p, q)
     während   nicht  (p.end ()  und  q.end ())
        tree = mergeTree (p.currentTree (), q.currentTree ())
        
         if   not  heap.currentTree (). Empty ()
            tree = mergeTree (tree, heap.currentTree ())
        
        heap.addTree (Baum)
        heap.next (); p.next (); q.next ()

Einfügen [ Bearbeiten ]

Sie können ein neues Element in einen Heap einfügen, indem Sie einfach einen neuen Heap erstellen, der nur dieses Element enthält, und ihn dann mit dem ursprünglichen Heap zusammenführen . Aufgrund der Zusammenführung benötigt das Einfügen die Zeit O (log n ). In einer Reihe von n aufeinanderfolgenden Insertionen hat Insert jedoch eine abgeschriebene Zeit von O (1) (d. H. Konstant).

Find minimum [ edit ]

Um das minimum -Element des Haufens zu finden, suchen Sie das Minimum unter den Wurzeln der Binomialbäume. Dies kann wieder leicht in O (log n ) Zeit gemacht werden, da es nur O (log n ) Bäume gibt und somit Wurzeln zu untersuchen.

Durch Verwenden eines Zeigers auf den Binomialbaum, der das Minimalelement enthält, kann die Zeit für diese Operation auf O (1) reduziert werden. Der Zeiger muss aktualisiert werden, wenn eine andere Operation als Minimum suchen ausgeführt wird. Dies kann in O (log n ) durchgeführt werden, ohne die Laufzeit einer Operation zu erhöhen.

Lösche Minimum [ edit ]

Um das Minimum-Element aus dem Haufen zu löschen, finde zuerst dieses Element, entferne es aus seinem Binomialbaum und erhalte a Liste seiner Teilbäume. Dann transformieren Sie diese Liste von Teilbäumen in einen separaten Binomialhaufen, indem Sie sie von der kleinsten in die größte Reihenfolge umordnen. Führen Sie dann diesen Haufen mit dem ursprünglichen Haufen zusammen. Da jede Wurzel höchstens log n Kinder hat, ist das Erstellen dieses neuen Heaps O (log n ). Das Zusammenführen von Heaps ist O (log n ), daher ist die gesamte Löschmindestoperation O (log n ).

 Funktion  deleteMin (Heap)
    min = heap.trees (). first ()
     für jeden  aktuellen  in  heap.trees ()
         Wenn  current.root <min.root dann  min = current
     für jeden  Baum  in  minTrees ()
        tmp.addTree (Baum)
    heap.removeTree (min)
    Zusammenführen (Heap, tmp)

Schlüssel verkleinern Bearbeiten

Nachdem der Schlüssel eines Elements verkleinert wurde, kann er kleiner als der Schlüssel des übergeordneten Elements werden, wodurch der Minimum-Heap verletzt wird Eigentum. Wenn dies der Fall ist, tauschen Sie das Element mit dem übergeordneten Element und möglicherweise auch mit dem übergeordneten Element usw. aus, bis die Minimum-Heap-Eigenschaft nicht mehr verletzt wird. Jeder Binomialbaum hat eine Höhe von höchstens log n daher dauert dies O (log n ).

Löschen [ Bearbeiten ]

Um ein Element aus dem Heap zu löschen, verringern Sie seinen Schlüssel auf negative Unendlichkeit (dh einen Wert, der niedriger ist als ein Element in den Haufen) und löschen Sie dann das Minimum im Haufen.

Zusammenfassung der Laufzeiten [ edit ]

Hier sind Zeitkomplexitäten [2] verschiedener Heap-Datenstrukturen. Funktionsnamen setzen einen Min-Heap voraus. Zur Bedeutung von " O ( f )" und " Θ ( f )" siehe Big O-Notation.

Anwendungen Bearbeiten

Siehe auch [ ]

[

  1. ^ Vuillemin, Jean (1. April 1978) ). Msgstr "Eine Datenstruktur zum Manipulieren von Prioritätswarteschlangen". Mitteilungen der ACM . 21 (4): 309–315. CiteSeerX 10.1.1.309.9090 . doi: 10.1145 / 359460.359478. ISSN 0001-0782.
  2. ^ a b c ] d Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Einführung in Algorithmen (1. Aufl.). MIT Press und McGraw-Hill. ISBN 0-262-03141-8 .
  3. ^ Fredman, Michael Lawrence; Tarjan, Robert E. (Juli 1987). "Fibonacci-Heaps und ihre Verwendung in verbesserten Algorithmen zur Netzwerkoptimierung" (PDF) . Zeitschrift der Association for Computing Machinery . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi: 10.1145 / 28869.28874.
  4. ^ Iacono, John (2000), "Verbesserte Obergrenzen für die Paarung von Haufen", Proc. 7. Skandinavischer Workshop zur Algorithmentheorie (PDF) Lecture Notes in Computer Science, 1851 Springer-Verlag, S. 63–77, arXiv: 1110.4428 CiteSeerX 10.1.1.748.7812 doi: 10.1007 / 3-540-44985-X_5, ISBN 3-540-67690-2
  5. ^ Fredman, Michael Lawrence (Juli 1999). "Über die Effizienz der Paarung von Haufen und verwandten Datenstrukturen" (PDF) . Zeitschrift der Association for Computing Machinery . 46 (4): 473–501. doi: 10.1145 / 320211.320214.
  6. ^ Pettie, Seth (2005). Auf dem Weg zu einer endgültigen Analyse von Paarungshaufen (PDF) . FOCS '05 Proceedings of the 46. Annual IEEE Symposium on Foundations of Computer Science. S. 174–183. CiteSeerX 10.1.1.549.471 . doi: 10.1109 / SFCS.2005.75. ISBN 0-7695-2468-0 .
  7. ^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF) ] Proc. 7. jährliches ACM-SIAM-Symposium über diskrete Algorithmen S. 52–58
  8. ^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Bottom-Up-Heap-Konstruktion". Datenstrukturen und Algorithmen in Java (3. Aufl.). S. 338–341. ISBN 0-471-46983-1 .
  9. ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rangpaarungshaufen" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. doi: 10.1137 / 100785351.
  10. ^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strenge Fibonacci-Haufen (PDF) . Vorträge des 44. Symposiums zur Theorie des Rechnens – STOC '12. S. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi: 10.1145 / 2213977.2214082. ISBN 978-1-4503-1245-5 .

Externe Links [ bearbeiten ]


Leave a Reply

Your email address will not be published. Required fields are marked *