Die Funktion Heapify-Locally

Vorherige Seite Inhaltsverzeichnis Nächste Seite

heapify_locally in Struktur

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

  • Kurzbeschreibung

    Stellt die Heapordnung für den Knoten k her.
    Rückgabe: neue Position des k-Schlüssels oder Null, wenn nicht bewegt.

    Schnittstelle

    Parameter

    Explizite Parameter: Wurzel k des Knoten, der heapgeordnet werden soll.
    Implizite Parameter: Keine.

    Vorbedingung

    - (keine)

    Heapify-Locally Start
    Knoten Bedeutung
    Grauer Knoten Verletzt möglicherweise die Heapbedingung.

    Nachbedingung

    Der Knoten k ist heapgeordnet.

    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.

    Die Heapordnung für den Knoten k ist in der folgenden Grafik dargestellt.

    Heapordnung am Knoten

    Je nach Belegung der Datensätze mit Werten ergeben sich Unterschiedliche Ziele für die Aufgaben. Für die ersten drei Datensätze sind die Ziele in den folgenden Grafiken dargestellt.

    Heapify-Locally Ziel 1 Heapify-Locally Ziel 1 Heapify-Locally Ziel 1
    Knoten Bedeutung
    Schlüssel Knoten Größe des Schlüssels.

    Realisierung

    Hilfsfunktionen

    Funktion (Parameter) Kurzbeschreibung Vorbedingung
    Compare(Knoten a,b) Vergleicht die Schlüssel der Knoten a und b. Im Applet werden die Schlüssel sichtbar und zwischen den Knoten erscheint ein Relationszeichen. - (keine)
    Swap(Knoten a,b) Vertauscht die Schlüssel der Knoten a und b. - (keine)

    Aufgabe

    In der Aufgabe ist der Knoten k mit seinen beiden Sohnknoten dargestellt. Stellen Sie die Heapordnung für den Knoten k her.

    Versuchen Sie mit möglichst wenig Schritten zur Lösung zu kommen.

    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: Es gibt keine Einschränkungen.

    Das Standardverfahren: Es wird ermittelt, welcher Sohnknoten den größeren Schlüssel hat. Der Wurzelknoten muss nur mit diesem Knoten verglichen werden. Ist der Wurzelschlüssel kleiner als der größere Schlüssel der Sohnknoten, wird er mit diesem vertauscht. Wurde der Wurzelschlüssel bewegt, wird seine neue Position zurückgegeben, sonst der spezielle Wert Null.

    Laufzeit: Vergleiche (Compare): 2. Vertauschungen (Swap): 1.

    Korrektheit: Wird vertauscht, so ist der neue Wurzelschlüssel auch größer oder gleich dem zweiten Sohnschlüssel. Der neue Wurzelschlüssel ist größer als der alte Wurzelschlüssel. Wird nicht vertauscht, so war die Heapordnung bereits erfüllt.


    Vorherige Seite Inhaltsverzeichnis Nächste Seite