A D T   H e a p

Beispielprogramm 2:   Heapsort




PROGRAM  heap_anwendung_2;{
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Anwendungsbeispiel "Heapsort", HMO, Warendorf, Juni 1988 / Dez. 1994

Verwenden Sie den ADT Heap für ein Programm, das ein Array sortieren kann.
Benutzen Sie als Array direkt das Array im Heap. Verfassen Sie eine
entsprechende Eingabe- und Ausgabeprozedur. Der Sortieralgorithmus soll
folgendermaßen ablaufen:
- mache aus dem Array einen Maximum-Heap
- laufe vom letzten Platz im Array bis zum 2.Platz und
  - nehme das aktuelle Maximum vom Heap,
  - entferne das Maximum vom Heap,
  - schreibe das Maximum an die gerade aktuelle Position.
Begründe, warum dieser Algorithmus funktioniert. Vergleiche die Anzahl der
Vergleichsoperationen bei diesem "Heapsort" mit den Dir bekannten
Sortierverfahren. Zusatz für Experten: bestimme die Anzahl der Vergleiche
in der O-Notation. }

CONST     n_heap       = 1000;      {Integer, max. Heapgröße}
TYPE      inhalt_heap  = Integer;   {Inhalt der Heapknoten incl. Bewertung}

FUNCTION  kleinergleich (b,a: inhalt_heap): Boolean;
BEGIN     kleinergleich:=(b<=a)  END;

FUNCTION  groessergleich (b,a: inhalt_heap): Boolean;
BEGIN     groessergleich:=(b>=a)  END;

{$I HPADT.PAS}

VAR  heap: heap_typ;

  {1}
  PROCEDURE eingabe_array (VAR h: heap_typ);
  VAR i: Integer;
  BEGIN
    Writeln('BEISPIEL 2 zum ADT HEAP :  H E A P S O R T');
    Writeln('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~');
    Writeln('Eingabe eines Arrays mit 15 Integer-Elementen:');
    FOR i:=1 TO 15 DO
    BEGIN Write(i:2,' : '); Readln(h.feld[i]) END;
  END;

  {2}
  PROCEDURE ausgabe_array (VAR h: heap_typ);
  VAR i: Integer;
  BEGIN
    Writeln; Write ('ARRAY : ');
    FOR i:=1 TO 15 DO Write(h.feld[i]:4); Writeln
  END;

  {3}
  PROCEDURE heapsort (VAR h: heap_typ);
  VAR index : Integer;
      bestes: inhalt_heap;
  BEGIN
    make_heap (heap,15,max_heap);
    FOR index := 15  DOWNTO  2  DO
    BEGIN
      best_heap(heap,bestes);
      delbest_heap(heap);
      heap.feld[index] := bestes
    END
  END;

BEGIN
  eingabe_array (heap);
  ausgabe_array (heap);
  heapsort (heap);
  ausgabe_array (heap)
END.




HTML-Texte: Heapoperationen Heapsort Priority Queue Branch & Bound ADT Heap HAUPTTEXT
Paket mit Pascal-Dateien laden: HeapPac.Zip   (39 K)

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998