Die Funktion Heapify

Vorherige Seite Inhaltsverzeichnis Nächste Seite

heapify in Struktur

  • Kurzbeschreibung
  • Schnittstelle
  • Parameter
  • Vorbedingung
  • Nachbedingung
  • Realisierung
  • Hilfsfunktionen
  • Aufgabe
  • Bedienungstipps
  • Das Applet
  • Lösung

  • Kurzbeschreibung

    Stellt die Heapordnung für den Baum mit Wurzel k her.

    Schnittstelle

    Parameter

    Explizite Parameter: Wurzel k des Teilbaums, der heapgeordnet werden soll.
    Implizite Parameter: Heapbaum

    Vorbedingung

    Sohnbäume unter k: heapgeordnet.

    Heapify Start
    Knoten Bedeutung
    Grauer Knoten Enthält Schlüssel aus Wurzel. Verletzt möglicherweise die Heapbedingung.
    Grüner Knoten Erfüllt die Heapbedingung.
    Hellgrauer Knoten Nicht beteiligt.

    Nachbedingung

    Der Baum mit der Wurzel k ist heapgeordnet.

    Heapify Ziel
    Knoten Bedeutung
    Grüner Knoten Erfüllt die Heapbedingung.
    Hellgrauer Knoten Nicht beteiligt.

    Realisierung

    Hilfsfunktionen

    Funktion (Parameter) Kurzbeschreibung Vorbedingung
    Heapify-Locally (Knoten k) Stellt die Heapordnung für den Knoten k her.
    Rückgabe: neue Position des k-Schlüssels oder Null, wenn nicht bewegt.
    - (keine)

    Heapify-Locally(Knoten k) stellt die Heapordnung für den Knoten k (zwischen k und seinen beiden Sohnknoten) her. Wenn nötig, vertauscht es den Schlüssel bei k mit einem der beiden Sohnknoten und liefert die Position des Sohnknotens zurück, in dem der Schlüssel nun ist. War keine Vertauschung nötig, so teilt die Funktion Heapify-Locally dies mit, indem sie einen sogenannten Null-Wert zurückliefert.

    Aufgabe

    In der Aufgabe ist ein Teilbaum hervorgehoben, der von Ihnen heapgeordnet werden soll. Die hellgrauen Knoten werden in dieser Aufgabe nicht bearbeitet. Die Wurzel des Teilbaums ist eventuell nicht heapgeordnet und daher dunkelgrau dargestellt. Knoten, von denen der Algorithmus weiß, dass sie heapgeordnet sind, sind grün markiert. Der Schlüssel, der anfangs in der Wurzel des Teilbaums ist, heißt Wurzel-Schlüssel. Seine Position ist rot umrandet. Liefert Heapify-Locally den Null-Wert zurück, verschwindet die rote Umrandung.

    Je nachdem, welche Schlüssel in den Knoten gespeichert sind, ergibt sich ein anderer Ablauf. Lösen Sie die Aufgabe daher für jeden der Datensätze.

    Bedienungstipps

    Das Applet

    Fehler: Ihr Browser unterstützt kein JAVA!

    Lösung

    Erlaubte Reihenfolgen: Für diese Funktion gibt es nur eine mögliche Reihenfolge.

    Das Standardverfahren: Bis auf die Wurzel ist der gesamte Teilbaum heapgeordnet. Nur der Schlüssel an der Wurzel verletzt möglicherweise die Heapbedingung. Mit Hilfe von Heapify-Locally wird der Schlüssel solange "nach unten" bewegt, bis er "passt". Sobald Heapify-Locally feststellt, dass der Schlüssel an seiner aktuellen Position die Heapbedingung erfüllt, endet die Funktion Heapify. Dies ist spätestens der Fall, wenn der Schlüssel einen Blattknoten erreicht hat.

    Laufzeit: Es sind höchstens so viele Aufrufe von Heapify-Locally nötig, wie der Baum hoch ist.

    Korrektheit: Zu jedem Zeitpunkt verletzt höchstens ein Knoten die Heapbedingung. Dies bleibt gewährleistet, da der nach oben verschobene Schlüssel aus dem Sohnknoten die Heapbedingung einhält. Wenn der Aufruf von Heapify-Locally ergibt, dass der Wurzel-Schlüssel die Heapbedingung einhält, so gilt die Heapbedingung im ganzen Teilbaum.

    Implementierung: Es reicht, die Schlüssel aus den Sohnknoten hochzuziehen und den Wurzel-Schlüssel erst an seiner endgültigen Position dem Knoten zuzuweisen.


    Vorherige Seite Inhaltsverzeichnis Nächste Seite