Die Funktion Heapsort

Vorherige Seite Inhaltsverzeichnis Nächste Seite

heapsort in Struktur

  • Kurzbeschreibung
  • Schnittstelle
  • Parameter
  • Vorbedingung
  • Nachbedingung
  • Realisierung
  • Hilfsfunktionen
  • Aufgabe
  • Bedienungstipps
  • Das Applet
  • Lösung
  • In der Grafik sehen Sie den Platz der Funktion in der funktionalen Struktur des Heapsort-Algorithmus.

    Die Funktion Heapsort wird von keiner Funktion des Algorithmus aufgerufen. Nur sie wird von außen aufgerufen, und dient somit als Einstiegsfunktion in den Algorithmus.

    Ein Programm, dass Daten mit dem Heapsort-Algorithmus sortieren will, stellt sie in einem Array bereit. Aufgrund der Implementierung der Datenstruktur erscheint das Array für den Algorithmus als Heapbaum. Dann ruft es die Heapsort-Funktion auf, die die Daten sortiert und in der Ergebnisliste ablegt. Von dort kann das Programm sie entnehmen und weiterverarbeiten.


    Kurzbeschreibung

    Sortiert die Eingabedaten.

    Dies ist die Einstiegsfunktion für den Heapsort-Algorithmus.

    Schnittstelle

    Die Schnittstelle beschreibt, was ein Nutzer der Funktion wissen muss. Sie umfasst die Parameter, Vorbedingung und die Nachbedingung.

    Parameter

    Explizite Parameter: Keine.
    Implizite Parameter: Heapbaum und Ergebnisliste.

    Parameter geben an, auf welchem Teil der Datenstruktur die Funktion arbeiten soll. Explizite Parameter werden beim Funktionsaufruf übergeben und steuern damit die Funktion direkt. Unabhängig von diesen kennt die Funktion schon bestimmte Teile der Datenstruktur und begrenzt ihre Arbeit auf diese Teile. Diese werden implizite Parameter genannt, da sie nicht beim Aufruf übergeben werden, aber doch das Verhalten der Funktion beeinflussen.

    Vorbedingung

    Heapbaum: vollständig und voll gefüllt.
    Ergebnisliste: leer.

    Es wird aber nicht gefordert, dass die Knoten heapgeordnet sind!

    Die Vorbedingung beschreibt, wann eine Funktion angewendet werden kann. Sie ist als Bedingung über der Datenstruktur formuliert.

    Heapsort Start
    Knoten Bedeutung
    Grauer Knoten Verletzt möglicherweise die Heapbedingung.
    Grüner Knoten Erfüllt die Heapbedingung.
    Leerer Knoten Leer.

    Die obige Grafik zeigt einen Zustand der Datenstruktur, der die Vorbedingung erfüllt. Später werden Sie eine Aufgabe bearbeiten, die mit diesem Zustand beginnt.

    Aus der Implementierung der Datenstruktur ergibt sich, dass die Vorbedingung erfüllt ist, sobald die Daten vollständig bereitstehen.

    Nachbedingung

    Heapbaum: Leer.
    Ergebnisliste: Aufsteigend geordnet und voll gefüllt.

    Die Nachbedingung beschreibt, was die Funktion bewirkt. Sie formuliert welche logischen Bedingungen auf der Datenstruktur gelten, nachdem die Funktion aufgerufen wurde.

    Heapsort Ziel
    Knoten Bedeutung
    Schlüssel Knoten Größe des Schlüssels.
    Leerer Knoten Leer.

    Die obige Grafik zeigt einen Zustand der Datenstruktur, der die Nachbedingung erfüllt. Später werden Sie eine Aufgabe bearbeiten, bei der Sie die Datenstruktur in diesem Zustand bringen sollen.

    Damit ist der Heapsort-Algorithmus vollständig abgearbeitet und die Daten liegen sortiert bereit.

    Realisierung

    Die Realisierung behandelt, wie die Funktion intern arbeitet. In diesem Lernprogramm wird die Realisierung auf einem relativ abstrakten Niveau beschrieben. Es werden aber auch Hinweise zur Implementierung in einer Programmiersprache gegeben.

    Hilfsfunktionen

    Diese Funktion ruft andere Funktionen als Hilfsfunktionen auf, um ihre Aufgabe zu erledigen. Es ist daher wichtig, die Schnittstellen der Hilfsfunktionen zu kennen.

    Funktion (Parameter) Kurzbeschreibung Vorbedingung
    Build-Heap () Stellt die Heapordnung für den gesamten Heapbaum her. Heapbaum: vollständig und voll gefüllt.
    Sort () Verschiebt alle Schlüssel des Heapbaums in die Ergebnisliste. Heapbaum: vollständig, voll gefüllt und heapgeordnet.
    Ergebnisliste: leer.

    Aufgabe

    Jetzt sind Sie an der Reihe! Finden Sie heraus, welche Schritte diese Funktion ausführen muss. Dazu steht Ihnen unten eine interaktive Aufgabe (Java-Applet) zur Verfügung. Im Applet ist die Datenstruktur mit einem Satz Daten belegt. Rufen Sie die Hilfsfunktionen auf, indem Sie auf die Buttons mit den Funktionsnamen drücken. Sie müssen die Datenstruktur in den Zustand der Nachbedingung bringen.

    Bedienungstipps

    Das Applet

    Fehler: Ihr Browser unterstützt kein JAVA!

    Lösung

    Lassen Sie sich den Pseudocode der Funktion anzeigen, indem Sie das Applet in den Modus "Animation" umschalten. Über die Buttonleiste am Fuß des Applets gehen Sie die Schritte der Lösung einzeln durch. Zu jedem Schritt erscheint ein kurzer Hinweistext.

    Der Heapsort-Algorithmus arbeitet in zwei Phasen:

    1. Build-Heap stellt die Heapeigenschaft im Heapbaum her
    2. Sort bewegt alle Schlüssel in die Ergebnisliste

    Sort kann nicht zuerst aufgerufen werden, da seine Vorbedingung erfordert, dass der Heapbaum heapgeordnet ist.


    Vorherige Seite Inhaltsverzeichnis Nächste Seite