Wir verwenden Heaps als Datenstruktur, wenn wir Sortierungsalgorithmen nutzen wollen. Sie sind eine andere Art der Binary Trees, nur mit einigen zusätzlichen Regeln hinsichtlich der Form des Baumes und der Reihenfolge der Baumknoten. Heaps sind komplette Binary Trees, was bedeutet, dass sie in jedem Level alle Knoten haben. Sie gelten als komplett, wenn, von links nach rechts gelesen, keine Lücke in einem Level besteht. Jeder Knotenwert eines Heaps ist größer oder gleich des Wertes seiner Kinder. Heaps werden genutzt für das Sortieren von Daten (HeapSort), bei der Implementierung von Graph-Algorithmen (Shortest path), für Priority Queues oder für das Finden des kleinsten/größten K-Wert.
Arten von Heaps
MAX HEAP: Root-Node hat den größten Wert. Der Wert
jedes Knoten ist größer als der Wert seiner Kinder.
MIN HEAP: Root-Node hat den kleinsten Wert. Der Wert
jedes Knoten ist kleiner, als der Wert seiner Kinder.
BINARY HEAP: Ist ein Binary Tree
Heaps unterstützen aufgrund ihrer Struktur nicht das Nachschlagen von
Werten. Nur max/min können wir mit ihnen ausweisen. Mit einem Heap
können wir Elemente mit einer O(n*log n)-Time-Complexity sortieren und
auch Priority Queues erstellen.
GetMax() = O(1)
Insert = O(log n)
Remove = O(log n)