Hilfe Hauptseite Vorherige Naechste
Logo
Navigationsleiste
1. Der Binomial Heap Algorithmus / 4. Die Funktionen

4.5 Die Verkleinere Schlüssel-Funktion


Einleitung Es kann vorkommen, daß sich die Priorität eines im Priority Queue befindlichen Elements nachträglich ändert. Z.B. könnte einem Programm während der Ausführung eine höhere Priorität zugewiesen werden. In diesem Fall müßte der Schlüssel dieses Elements verkleinert werden.

Das Verkleinere Schlüssel - Applet Diese Situation ist im folgenden Beispiel eingetreten. Die Priorität des markierten Elements 18 ist auf 11 erhöht worden. Verändere den Binomial Heap nun so, wie es die Funktion "Verkleinere Schlüssel" tun würde. Dazu stehen Dir folgende Funktionen zur Verfügung:
Verkl.
Mit dieser Funktion kannst du den Schlüsselwert des markierten Elements um 1 verringern.
Bruder
Mit dieser Funktion kannst du das Element mit einem eventuell vorhandenen Bruderknoten vertauschen.
Vater
Hat der aktuelle Knoten einen Vater, so kannst du mit dieser Funktion das aktuelle Element mit dem Vater vertauschen.
Merken
Hat der aktuelle Knoten einen kleineren Wert als das bisherige Minimum, so kannst du dir mit dieser Funktion das neue Minimum merken.
Sohn
Hat der aktuelle Knoten mindestens einen Sohn, so kannst du mit dieser Funktion das aktuelle Element mit dem rechten Sohn vertauschen.
Fertig
Mit diesem Button kannst du dem Applet mitteilen, daß du den Binomial Heap aktualisiert hast. Dir wird dann mitgeteilt, ob der Binomial Heap jetzt korrekt ist.
Auswahlmenü
Mit dem Auswahlmenü kannst du zwischen den verschiedenen Beispielen wählen und die aktuelle Aufgabe in den Ausgangszustand zurücksetzen.

Das Verkleinern - Applet

Die Verkleinere Schlüssel - Funktion Wie du vielleicht bemerkt hast, benötigt die Verkleinere Schlüssel-Funktionen nur die Funktionen "Verkl." und "Vater". Mit "Verkl." wird der Schlüssel des Elements auf die neue Priorität geändert. Ist danach die Heapordnung verletzt, wird das Element mit Hilfe der Funktion "Vater" so lange mit dem Vaterknoten vertauscht, bis es sich an der richtigen Position befindet.

Wie bereits in Kapitel 4.4 beschrieben, wird die Funktion "Verkleinere Schlüssel" von der nun in Kapitel 4.6 behandelten "Element Entfernen"-Funktion verwendet.

1. Der Binomial Heap Algorithmus / 4. Die Funktionen
Seitenanfang Vorherige Naechste
Navigationsleiste