7

PI (Subject) / Heap (Lesson)

This lesson was created by blace.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• Was ist ein Heap und was ist die Heapbedingung? Ein Heap ist ein binärer baum mit einer Heap Bedingung. Die Heapbedingung bestimmt die Sortierung des Heaps mit entweder max Heap - bei welchem die Werter aller Kindknoten kleiner oder gleich dem Knotenwert sind. min Heap - bei welchem die Werte aller Kindknoten größer oder gleich dem Knotenwert sind. alle Ebenen bis auf die letzte müssen vollständing gefüllt sein und die letzte Ebene wird linksbündig gefüllt.
• Erläutere an einem Beispiel, wie das Versickern in einem Heap funktioniert. Beispiel Heap:                               1                    7                     6             3             4         5         2 Max Heap als Heap Bedingung Die Wurzel versickert, indem sie mit dem größeren der beiden Kindknoten die plätze tauscht, solange einer der Kindknoten größer als die Wurzel ist                                 7                        1                       6                3            4            5           2                                7                       4                         6               3          1                5          2
• Wie kann ein Heap als Array realisiert werden? Wenn man ein Heap als Array realisieren möchte ist die Heapbedingung für einen max Array ki >= k2i und ki >= 2i+1 ( falls 2i und 2i+1 <= n) Dies bedeutet, dass der Linke nachfolger an 2i und der rechte Nachfolger an 2i+1 liegt z.B.  Max Heap             6 4                  5 1     2      3 6     4      5 Dies gilt allerdings nur für einen Array der beim Index 1 anfängt. Wenn ein Array, wie üblich, bei 0 anfängt ist der Linke nachfolger bei 2i+1 und der rechte bei 2i+2
• Wie funktioniert das Einfügen in einen Heap und wie wird danach die Heapbedingung wieder hergestellt? Ein einzufügendes Element wird an die erste freie Position eingefügt, also links in der untersten Ebene. Die Heapbedingung wird dann mittels upHeap hergestellt, indem das Element seinen vaterknoten untersucht und, bei einem MaxHeap wenn es größer ist und bei einem MinHeap wenn es kleiner ist, mit diesem die Position tauscht, bis dies nicht mehr der Fall ist.
• Wie funktioniert das Löschen in einem Heap und wie wird danach die Heapbedingung wieder hergestellt? Zuerst entfernt man das zu löschende Element, dann fügt man an dieser Position das letzte Element ein und lässt dieses dann versickern
• Wie funktioniert Heapsort? Man baut einen Heap auf, indem man das neue Element nach vorne in das Array schreibt und versickern lässt, dies ist dann ähnlich wie beim Einfügen, sodass das Array vom ende her wächst. Dadurch wird auch die Heap Bedingung eingehalten. Dann wird der Heap geleert und statt, dass die Elemente ausgegeben werden wird das entnommene Element nach hinten angefügt. Die Wurzel wird immer nach ganz hinten gestellt.
• Warum ist ein Heap zur Realisierung einer Vorrang-/Prioritätswarteschlange geeignet? Bei einer Proritätswarteschlange werden Elemente nach ihrer Priorität sortiert, sodass wichtigere elemente früher drankommen. Da man bei einem Heap eine sehr ähnliche Sortierung vornimmt werden solche Prioritätswarteschlangen oft mit Heaps implementiert

back  |  next 1 / 1