Heaps & Priority Queues

Summary

In diesem Video wird die Funktionsweise von Heaps und ihrer Anwendung in der Prioritätswarteschlange erklärt. Heaps sind semi-ordentliche, baumartige Datenstrukturen, die entweder in einer Max-Heap (größtes Element oben) oder Min-Heap (kleinstes Element oben) organisiert sind. Es werden grundlegende Operationen wie das Einfügen und Entfernen von Elementen behandelt, wobei jeweils die Heap-Eigenschaften aufrechterhalten werden. Die Implementierung von Heaps mit Arrays wird erläutert, einschließlich der Verwendung von Formeln zur Bestimmung von Eltern- und Kindknoten. Abschließend wird gezeigt, wie Heaps als Grundlage für eine effiziente Prioritätswarteschlange dienen können.

Takeaways

• 😀 Ein Heap ist eine halb geordnete Baumstruktur, die besonders effizient für die Implementierung einer Prioritätswarteschlange ist.
• 😀 In einem Max-Heap ist der Wert des Elternknotens immer größer als der seiner Kinder, während in einem Min-Heap der Wert des Elternknotens kleiner ist als der seiner Kinder.
• 😀 Heaps garantieren nur eine Ordnung zwischen Eltern und Kindern (und deren Nachkommen), nicht jedoch zwischen Geschwistern oder auf verschiedenen Ebenen des Baums.
• 😀 In einem Heap ist die Reihenfolge von links nach rechts innerhalb einer Ebene beliebig und hat keinen Einfluss auf die Heap-Eigenschaft.
• 😀 Bei der Einfügeoperation wird ein neues Element an der höchsten und dann linksmost verfügbaren Position eingefügt und dann durch „Hochschwimmen“ des Elements an die richtige Stelle gebracht.
• 😀 Beim Entfernen eines Elements wird das Element an der obersten Stelle entfernt und durch das niedrigste, rechtseste Element ersetzt, woraufhin das Element durch „Absinken“ an die richtige Stelle gelangt.
• 😀 Ein Heap kann als Array dargestellt werden, wobei der Index des ersten Elements den Wurzelknoten enthält und die Kinder sowie Eltern mit einfachen mathematischen Formeln gefunden werden können.
• 😀 Die Indexformeln für Eltern und Kinder in einem Heap sind: Der Elternknoten eines Indexes `i` ist bei Index `i//2`, das linke Kind ist bei `2*i` und das rechte Kind bei `2*i + 1`.
• 😀 Eine Prioritätswarteschlange kann direkt mit einem Heap umgesetzt werden, wobei beim Einfügen von Elementen das Element in den Heap eingefügt und beim Entfernen das oberste Element entnommen wird.
• 😀 Bei der Implementierung eines Heaps in Code ist es wichtig, darauf zu achten, dass der Array-Speicherplatz bei Bedarf vergrößert wird, indem beispielsweise die Array-Größe verdoppelt wird.

Q & A

Was ist ein Heap und wofür wird er verwendet?

Ein Heap ist eine halbgeordnete Baumstruktur, die sehr effizient zur Implementierung von Prioritätswarteschlangen genutzt wird. Er kann als Max-Heap oder Min-Heap konzipiert sein, wobei im Max-Heap das größte Element oben steht und im Min-Heap das kleinste Element oben.

Was bedeutet es, dass ein Heap 'halbgeordnet' ist?

Ein Heap ist halbgeordnet, weil die Reihenfolge der Elemente nur innerhalb von Eltern und deren direkten Nachkommen garantiert ist, aber nicht unbedingt auf den verschiedenen Ebenen des Heaps. Es gibt keine feste Reihenfolge zwischen den Ebenen.

Wie funktioniert die 'Swim-up'-Operation in einem Max-Heap?

Die 'Swim-up'-Operation wird verwendet, wenn ein neues Element in den Heap eingefügt wird. Das Element wird nach oben verschoben, indem es mit seinem Elternteil getauscht wird, bis die Max-Heap-Eigenschaft erfüllt ist, also das Element nicht größer als sein Elternteil ist.

Was passiert, wenn beim Einfügen eines Elements in einen Max-Heap das Element kleiner ist als der Elternteil?

Wenn das eingefügte Element kleiner ist als der Elternteil, müssen keine Swaps durchgeführt werden, und die Max-Heap-Eigenschaft bleibt erhalten. In diesem Fall ist keine weitere Anpassung erforderlich.

Wie wird das Entfernen eines Elements aus einem Heap durchgeführt?

Beim Entfernen eines Elements, häufig des Wurzelelements, wird dieses durch das niedrigste und rechtsste Element im Heap ersetzt. Danach wird das neue Wurzelelement nach unten verschoben ('Sink-down'), um die Max-Heap-Eigenschaft wiederherzustellen.

Was ist die maximale Anzahl von Swaps, die erforderlich sind, um die Max-Heap-Eigenschaft nach dem Einfügen oder Entfernen eines Elements wiederherzustellen?

Im schlimmsten Fall sind nur so viele Swaps erforderlich, wie es Ebenen im Baum gibt. In einem vollständig ausgewogenen Baum ist die maximale Anzahl der Swaps log₂(n), wobei n die Anzahl der Elemente im Heap ist.

Warum wird empfohlen, beim Implementieren eines Heaps mit einem Array zu arbeiten?

Ein Array ermöglicht eine effiziente Verwaltung der Elemente im Heap, da die Positionen von Eltern und Kindern leicht berechnet werden können. Dies spart Speicher und erleichtert das Finden von Elementen.

Wie wird die Position des Elternteils und der Kinder in einem Heap-Array berechnet?

Die Position des Elternteils eines Elements an Index i kann mit der Formel i // 2 berechnet werden. Die Position des linken Kindes wird mit 2 * i berechnet, und die Position des rechten Kindes mit 2 * i + 1.

Warum wird der Index 0 im Array eines Heaps frei gelassen?

Der Index 0 wird frei gelassen, um die Berechnungen für die Positionen von Eltern und Kindern zu vereinfachen. Das Array beginnt mit Index 1, was die Verwendung der Formeln zur Berechnung der Eltern- und Kinderpositionen vereinfacht.

Wie funktioniert die Prioritätswarteschlange in Bezug auf einen Heap?

Eine Prioritätswarteschlange nutzt einen Heap als zugrunde liegende Datenstruktur. Beim Einfügen eines neuen Elements wird es im Heap eingefügt, und beim Entfernen wird das Element mit der höchsten oder niedrigsten Priorität (je nach Art des Heaps) entfernt.