Logo
Hilfe   Vorherige Seite Inhaltsverzeichnis Nächste Seite

1. Der Binomial Heap Algorithmus


Inhaltsverzeichnis
  1. Der Binomial Heap Algorithmus
  2. Vergleich des Binomial Heap Algorithmus mit anderen Algorithmen
  3. Der Binomial Heap
    3.1 Der Binomialbaum
    3.2 Die Binomial Heap Datenstruktur
  4. Die Funktionen des Binomial Heap Algorithmus
    4.1 Die Verschmelzen-Funktion (1)
    4.1 Die Verschmelzen-Funktion (2)
    4.2 Die Element Einfügen-Funktion
    4.3 Die Minimum Suchen-Funktion
    4.4 Die Minimum Entfernen-Funktion
    4.5 Die Verkleinere Schlüssel-Funktion
    4.6 Die Element Entfernen-Funktion
    4.7 Das Binomial Heap Applet
  5. Implementierung der Binomial Heap Datenstruktur
  6. Code-Erkennung
Weiter Informationen:

Einleitung Wann immer in einem System ein größerer Bedarf an Betriebsmitteln besteht als Betriebsmittel vorhanden sind, muß der Zugriff auf die Betriebsmittel koordiniert werden. Koordiniert werden muß z.B. die Verteilung von Rechenzeit eines Prozessors an verschiedene konkurrierende Programme oder die Abarbeitung von verschiedenen Druckaufträgen durch einen Drucker. Diese Koordinierung geschieht durch Einordnung der Prozesse oder Aufträge nach ihrer Priorität in eine Warteschlange und durch Abarbeitung des Auftrags mit der momentan höchsten Priorität. Diese Warteschlange wird "Priority Queue" genannt.

Der Priority Queue Nach Ottmann [Ottmann96] ist ein Priority Queue eine Datenstruktur zur Speicherung einer Menge von Elementen, für die eine Ordnung (Prioritätsordnung) definiert ist. Je nach Einsatzgebiet läßt sich die Prioritätsfunktion unterschiedlich definieren. Denkbar ist z.B. die Verwendung des Ankunftszeitpunkts eines Druckauftrags oder die Dringlichkeit der Ausführung eines Programms (z.B. könnte die Ausführung eines Betriebssystemprozesses dringlicher sein als die Ausführung einer normalen Anwendung).
Für die Verwaltung dieser Elemente in dieser Datenstruktur werden nun folgende Operationen benötigt:
  • Initialisieren: Mit dieser Funktion wird einfach ein neuer Queue erzeugt.
  • Einfügen eines Elements: Ein weiteres Element (Prozeß / Druckauftrag) möchte auf das Betriebsmittel (Prozessor / Drucker) zugreifen.
  • Minimum Suchen: Das als nächstes zu verarbeitende Element wird mit dieser Funktion gesucht.
  • Minimum Entfernen: Das als nächstes zu verarbeitende Element wird mit dieser Funktion aus der Warteschlange geholt.

In einigen Anwendungsfällen kann zusätzlich eine effiziente Verschmelzung zweier Priority Queues benötigt werden. Ein Beispiel wären Multiprozessor - Systeme, bei denen ein Prozessor zusätzlich zu seinen Prozessen auch die Prozesse eines anderen, möglicherweise überlasteten Prozessors übernehmen soll. Da diese Situation sehr häufig vorkommen kann, muß eine effiziente Implementierung eines Prozessqueues für dieses System die effiziente Verschmelzung zweier Priority Queues ermöglichen. Diese Verschmelzen - Funktion ist die Stärke des Binomial Heap Algorithmus.

Algorithmen zur Verwaltung des Priority Queues Zur Verwaltung eines Priority Queues existieren nun mehrere Ansätze. Neben dem hier behandelten Binomial Heap Algorithmus ist z.B. die Implementierung eines Priority Queues mit verketteten Listen oder mittels eines Binärbaums möglich. Diese Arten der Implementierung sollen hier aber nicht näher behandelt werden. Um aber die Vor- und Nachteile des Binomial Heap Algorithmus beurteilen zu können, soll er mit den alternativen Implementierungsformen verglichen werden.

Der Binomial Heap Algorithmus Inhalt dieser Lernumgebung ist nun der Binomial Heap Algorithmus. Um die Arbeitsweise des Algorithmus zu verstehen, sind zuerst zwei grundlegende Themengebiete zu betrachten:
  1. Als erstes muß verstanden werden, wie die Datenstruktur zur Speicherung der Daten aufgebaut ist.
  2. Danach werden die zur Verwaltung der Daten benötigten Funktionen behandelt.
Nachdem die grundlegende Arbeitsweise des Algorithmus verstanden wurde, sollen noch Implementierungsdetails näher untersucht werden:
  1. Die Implementierung der Binomial Heap Datenstruktur.
  2. Eine Zuordnungsaufgabe: Welche Code-Fragmente implementieren welche Funktion?
Diese Lernumgebung kann aber leider nur einen Einstieg in den Binomial Heap Algorithmus bieten. Für detailliertere Informationen sollten die Bücher von Ottmann [Ottmann96] und Cormen [Cormen90] herangezogen werden.

Didaktisches Konzept Zur Vermittlung der Inhalte wird das didaktische Konzept des "Strukturierten aktiven Lernens von Algorithmen" (SALA) von Nils Faltin verwendet. Dieses Konzept sieht vor, das einzelne Funktionen des Algorithmus unter Verwendung mehrerer Phasen vermittelt werden.
  • Begonnen wird mit der Vorstellung der Problemstellung.
  • Anschließend können vom Benutzer in einer Probierphase verschiedene Lösungsansätze ausprobieren werden.
  • Danach wird dem Benutzer die Standardlösung vermittelt.
  • Zum Schluß soll der Benuter in einer Übungsphase die Standardlösung einüben.
Das didaktische Konzept SALA wird im Artikel von Faltin [Faltin99] genauer beschrieben.


Seitenanfang Vorherige Naechste
Navigationsleiste