Die Funktion Move-Max

Vorherige Seite Inhaltsverzeichnis Nächste Seite

move_max in Struktur

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

  • Kurzbeschreibung

    Verschiebt den maximalen Schlüssel des Heapbaums in die Ergebnisliste.

    Schnittstelle

    Parameter

    Explizite Parameter: - (Keine).
    Implizite Parameter: Heapbaum, Ergebnisliste

    Vorbedingung

    Heapbaum: vollständig und heapgeordnet.
    Ergebnisliste: aufsteigend geordnet.

    Die Ergebnisliste kann leer sein oder schon Schlüssel enthalten.

    Move-Max Start
    Knoten Bedeutung
    Grüner Knoten Erfüllt die Heapbedingung.
    Leerer Knoten Leer.

    Nachbedingung

    Heapbaum vollständig und heapgeordnet. Ergebnisliste aufsteigend geordnet.

    Der maximale Schlüssel wurde aus dem Heapbaum in die Ergebnisliste verschoben. Daher enthält der Heapbaum einen Schlüssel weniger, die Ergebnisliste einen Schlüssel mehr.

    Move-Max Goal
    Knoten Bedeutung
    Grüner Knoten Erfüllt die Heapbedingung.
    Leerer Knoten Leer.
    Schlüssel Knoten Größe des Schlüssels.

    Realisierung

    Hilfsfunktionen

    Funktion (Parameter) Kurzbeschreibung Vorbedingung
    Heapify (Knoten k)  Stellt die Heapordnung für den Baum mit Wurzel k her. Sohnbäume unter k: heapgeordnet.
    Move(Knoten a,b) Bewegt den Schlüssel von Knoten a nach Knoten b. - (keine)

    Aufgabe

    Verschieben Sie den größten Schlüssel aus dem Heapbaum in die Ergebnisliste.

    Die Ergebnisliste ist aufsteigend geordnet. D.h. der größte Schlüssel kommt ganz nach rechts.

    Der Heapbaum muss am Ende die Heapbedingung erfüllen.

    Sie müssen nur einen Schlüssel in die Ergebnisliste verschieben, nicht alle.

    Bedienungstipps

    Das Applet

    Fehler: Ihr Browser unterstützt kein JAVA!

    Lösung

    Das Standardverfahren: Der größte Schlüssel des Heapbaums befindet sich an der Wurzel, da die größer-gleich-Relation transitiv ist. Er wird an das rechte Ende der Ergebnisliste bewegt (Move), da dort der Platz für das größte Element ist. Im Allgemeinen wird er links neben dem zuletzt eingefügten Schlüssel platziert. Die Lücke in der Wurzel wird mit dem hintersten Schlüssel des Heapbaums gefüllt (Move). Der hinterste Schlüssel ist der rechteste Schlüssel in der untersten noch belegten Ebene. Dadurch ist der Heapbaum wieder vollständig. Nur an der Wurzel kann die Heapordnung verletzt sein. Heapify wird an der Wurzel gestartet, und stellt die Heapordnung wieder her.

    Laufzeit: Move: 2. Heapify: 1.

    Korrektheit: Dadurch, dass der hinterste Schlüssel zur Wurzel bewegt wird, ist der Baum wieder vollständig und es entsteht nur ein Knoten, an dem die Heapordnung verletzt ist. Die Vorbedingung für Heapify ist dann erfüllt.

    Implementierung: Aufgrund der Implementierung der Datenstruktur können beide Verschiebungen (Move) durch eine Vertauschung (Swap) realisiert werden. Eine weitere Folge der Implementierung ist, dass nur der Knoten links neben dem zuletzt eingefügten Schlüssel in der Liste frei ist und nur dort der aus der Wurzel entnommene Schlüssel gespeichert werden kann.

    Erlaubte Reihenfolgen: Man kann die Lücke in der Wurzel auch mit einem anderen Schlüssel füllen. Man muss dann aber mehrmals Schlüssel bewegen und Heapify aufrufen, damit der Heapbaum vollständig und heapgeordnet ist. Dies ist ineffizient.


    Vorherige Seite Inhaltsverzeichnis Nächste Seite