Die Funktion Build-Heap

Vorherige Seite Inhaltsverzeichnis Nächste Seite

build_heap in Struktur

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

  • Kurzbeschreibung

    Stellt die Heapordnung für den gesamten Heapbaum her.

    Schnittstelle

    Parameter

    Explizite Parameter: Keine.
    Implizite Parameter: Heapbaum.

    Vorbedingung

    Heapbaum: vollständig und voll gefüllt.

    Build-Heap Start
    Knoten Bedeutung
    Grauer Knoten Verletzt möglicherweise die Heapbedingung.
    Grüner Knoten Erfüllt die Heapbedingung.

    Nachbedingung

    Heapbaum: vollständig gefüllt und heapgeordnet.

    Build-Heap Ziel
    Knoten Bedeutung
    Grüner Knoten Erfüllt die Heapbedingung.

    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.

    Aufgabe

    Stellen Sie im ganzen Heapbaum die Heapordnung her. Die Blattknoten sind per Definition heapgeordnet und daher grün markiert. Die anderen Knoten wurden vom Algorithmus noch nicht untersucht und sind daher eventuell nicht heapgeordnet (grau). Sobald ein Knoten von Ihnen heapgeordnet wird, wird er grün markiert.

    Bedienungstipps

    Das Applet

    Fehler: Ihr Browser unterstützt kein JAVA!

    Lösung

    Die Blätter sind heapgeordnet, da sie keine Sohnknoten haben, die gegen die Heapbedingung verstoßen könnten.

    Man berechnet die Position des letzten inneren Knotens, indem man vom letzten Knoten des Heapbaums zum Vaterknoten geht. Ein Knoten ist dann ein innerer Knoten, wenn er kein Blattknoten ist.

    Erlaubte Reihenfolgen: Man kann Heapify an einem Knoten nur aufrufen, wenn die beiden Bäume unter dem Knoten schon heapgeordnet sind. Es gibt mehrere Reihenfolgen von Heapify-Aufrufen, die diese Bedingung einhalten. Der Modus Simulation erlaubt alle gültigen Reihenfolgen. Z.B. können Sie bereits im ersten Schritt zwischen zwei Knoten wählen: den Knoten ganz links in der 3. Ebene von oben oder den rechten Knoten in der 2. Ebene.

    Standardverfahren notwendig: Die Funktionen eines Algorithmus müssen die Vorbedingung ihrer Hilfsfunktionen beachten. Im Allgemeinen gibt es mehrere erlaubte Reihenfolgen der Aufrufe der Hilfsfunktionen. Damit ein Algorithmus als Programm ausgeführt werden kann, muss eine Reihenfolge fest gewählt werden. Diese Reihenfolge heißt hier Standardverfahren. Man wählt eine Reihenfolge, die effizient (d. h. mit wenigen Schritten auskommt) und leicht zu programmieren ist.

    Das Standardverfahren beginnt beim letzten inneren Knoten und geht die Ebenen von unten nach oben durch. Innerhalb einer Ebene geht es von rechts nach links. Dadurch ist sichergestellt, dass die Sohnbäume eines Knotens schon heapgeordnet sind, wenn Heapify aufgerufen wird. Aufgrund der Implementierung der Datenstruktur lässt sich dies als eine einfache Wiederholungsanweisung (mit Integer-Decrement) programmieren. Sie können über den Modus "Animation" das Standardverfahren studieren.

    Lernkonzept: In einem typischen Lehrbuch erfahren Sie nur das Standardverfahren. In diesem Lernprogramm sollen Sie auch die Hintergründe erfahren und selbst herausfinden, wie es zu dem Standardverfahren kam. Deshalb sollen Sie sich Gedanken über Auswahl und Reihenfolge der Schritte einer Funktion machen. (Weiteres zum Lernkonzept).

    Modi des Applets: Bei diesem Applet können Sie besonders gut die Unterschiede zwischen den Modi Simulation, Üben und Animation erkennen. Probieren Sie die verschiedenen Modi doch einmal aus! Versuchen Sie jetzt die Aufgabe im Modus "Üben" zu lösen. Das Applet lässt Sie die Schritte dann nur in der Reihenfolge des Standardverfahrens ausführen. (Weiteres zur Bedienung der Applets).


    Vorherige Seite Inhaltsverzeichnis Nächste Seite