Hilfe Hauptseite Vorherige Naechste
Logo
Navigationsleiste
1. Der Binomial Heap Algorithmus

3. Der Binomial Heap


Einleitung In diesem Abschnitt soll behandelt werden, wie der Binomial Heap Algorithmus die von ihm verwalteten Elemente in einer Datenstruktur speichert.
Um die Verwaltung von Elementen in einem Priority Queue effizient realisieren zu können, muß die zugrundeliegende Datenstruktur einen möglichst schnelles Ausführen folgender Funktionen ermöglichen:
  • Einfügen eines Elements
  • Minimum Suchen
  • Minimum Entfernen
  • Verschmelzen
Inwieweit die Datenstruktur nun eine effiziente Implementierung dieser Funktionen ermöglicht, hängt auch von der Art der zu verwaltenden Daten ab. Beim Entwurf eines Priority Queues für Druckaufträge kann man z.B. davon ausgehen, daß der zuerst eintreffende Druckauftrag auch zuerst abgearbeitet werden soll. Die Folge ist, daß sich eintreffende Druckaufträge nur hinter den schon vorhandenen Druckaufträgen einordnen können. Deshalb ließe sich dieser Priority Queue einfach in Form einer verketteten Liste implementieren.
Soll der Priority Queue aber einen Prozeß-Queue eines Betriebssystems verwalten, so kann durch die unterschiedlichen Prioritäten der Prozesse oft der Fall eintreten, daß z.B. ein Systemprozeß sich nicht hinter die wartenden Anwendungsprozesse einreihen soll, sondern direkt als nächstes ausgeführt werden muß. Zur Implementierung einer Datenstruktur mit diesen Anforderungen ist eine verkettete Liste nun recht ungeeignet. Weiterhin könnte die effiziente Verschmelzung von verschiedenen Priority Queues benötigt werden. Eine auch für diesen Anwendungsfall effiziente Implementierungsform wäre der Binomial Heap. Doch wie ist diese Datenstruktur nun aufgebaut?

Der Binomialbaum Um den Binomial Heap definieren zu können, muß zuerst in 3.1 der Binomialbaum behandelt werden. Denn ein Binomial Heap ist ein Wald von Binomialbäumen. Das bedeutet, daß ein Binomial Heap aus mehreren Binomialbäumen bestehen kann, und das die Anzahl dieser im Binomial Heap gespeicherten Binomialbäume variabel ist.

Der Binomial Heap Nachdem der Aufbau eines Binomialbaums verstanden wurde, kann in 3.2 dann der Binomial Heap behandelt werden, bevor in Kapitel 4 die verschiedenen Funktionen, wie z.B. Minimum Suchen, eingeführt werden können.

1. Der Binomial Heap Algorithmus
Seitenanfang Vorherige Naechste
Navigationsleiste