Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99

11. Übung - abzugeben am 19. 1. 1999 in Ihrer Übungsgruppe

11.a Heap (Theorie)

Teil 1: Sie haben in der Vorlesung den Begriff "Heap" kennengelernt. Erklären Sie den Begriff "Heap" und vergessen Sie nicht, die in diesem Zusammenhang verwendeten Begriffe "Vater" und "Sohn" zu erklären.

Zeigen Sie für jede der folgenden Zahlenfolgen, ob es sich um einen Heap handelt oder nicht. Begründen Sie ihre Antwort vernünftig.

Teil 2: Nehmen Sie die obige Zahlenfolge 1, 2, 5, 4, 3, 7, 6, 8. Wenn diese kein Heap ist, korrigieren Sie durch Änderung aller der Heap-Bedingung widersprechenden Werte. Zeigen Sie dann auf Basis dieses Heaps, wie nach Entnahme des kleinsten Elementes durch das "Versickern" wieder ein Heap entsteht. Fügen Sie hierauf zu dem nach dem Löschen entstandenen Heap wieder den Wert 1 hinzu. Wie sieht der entstehende Heap aus?

11.b Heap (Programm)

  DEFINITION OF MODULE Sort;
    PROCEDURE HeapSort*(VAR a: ARRAY OF LONGINT; len: INTEGER);
    (* Sortiert die len Zahlen von a[0] bis a[len-1] aufsteigend *)
  END Sort.