Datenstruktur - Heap
Ein Heap ist eine spezielle vollständige Binärbaumstruktur, die die Heap-Ordnungseigenschaft erfüllt. Ein Heap garantiert nur die Größenbeziehung zwischen Eltern- und Kindknoten und erfordert keine strikte Reihenfolge zwischen linken und rechten Teilbäumen.
Definition und Speicherung des Heaps
Baumansicht (Max-Heap)
Array-Ansicht (kompakte Speicherung)
Elternknoten: (i-1)/2 | Linkes Kind: 2i+1 | Rechtes Kind: 2i+2
Vollständiger Binärbaum → natürlich für Arrays geeignet, kein Zeiger-Overhead
Sift Up (Einfügen) O(log n)
Neues Element am Ende platzieren → mit Elternknoten vergleichen → tauschen, falls größer → bis zur Spitze des Heaps wiederholen
Sift Down (Wurzel löschen) O(log n)
Letztes Element zur Wurzel verschieben → mit dem größeren Kind vergleichen → tauschen, falls kleiner → bis zum Blatt wiederholen
Zwei Arten von Heaps:
- Max-HeapJeder Elternknoten ≥ Kindknoten, Wurzelknoten ist der maximale Wert
- Min-HeapJeder Elternknoten ≤ Kindknoten, der Wurzelknoten ist der minimale Wert
Da ein Heap ein vollständiger Binärbaum ist, eignet er sich natürlicherweise für die Speicherung in einem Array:
| Knoten (Index i) | Beziehung | Position (0-basiert) |
|---|---|---|
| Elternknoten | parent(i) | (i - 1) / 2 |
| Linker Kindknoten | left(i) | 2 * i + 1 |
| Rechter Kindknoten | right(i) | 2 * i + 2 |
Einfügen und Löschen im Heap (Heapify-Prozess)
Beispiel
#define MAX 100
/* Max-Heap-Struktur */
struct MaxHeap {
int arr[MAX];
int size; /* Aktuelle Anzahl der Elemente */
};
void initHeap(struct MaxHeap* h) { h->size = 0; }
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Hochsickern: das neu eingefügte Element von unten nach oben anpassen
Vergleiche mit dem Elternknoten; falls größer als der Elternknoten, tauschen; wiederhole, bis die Heap-Ordnung erfüllt ist */
void siftUp(struct MaxHeap* h, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (h->arr[idx] <= h->arr[parent]) break;
swap(&h->arr[idx], &h->arr[parent]);
idx = parent;
}
}
/* Einfügen: Zuerst das Element am Ende platzieren, dann mit Sift-up O(log n) anpassen */
void insert(struct MaxHeap* h, int value) {
if (h->size >= MAX) return;
h->arr[h->size] = value;
siftUp(h, h->size);
h->size++;
}
/* Sift Down: von der Wurzel nach unten anpassen
Mit dem größeren Kindknoten vergleichen; wenn kleiner, tauschen; wiederholen, bis die Heap-Eigenschaft erfüllt ist */
void siftDown(struct MaxHeap* h, int idx) {
while (1) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < h->size && h->arr[left] > h->arr[largest])
largest = left;
if (right < h->size && h->arr[right] > h->arr[largest])
largest = right;
if (largest == idx) break;
swap(&h->arr[idx], &h->arr[largest]);
idx = largest;
}
}
/* Wurzel löschen (Maximalwert): das letzte Element nach oben verschieben, dann mit Sift-down O(log n) anpassen */
int extractMax(struct MaxHeap* h) {
if (h->size == 0) return -1;
int maxVal = h->arr[0];
h->arr[0] = h->arr[--h->size]; /* Letztes Element nach oben verschieben */
siftDown(h, 0); /* Sift-down-Anpassung */
return maxVal;
}
int main() {
struct MaxHeap h;
initHeap(&h);
int vals[] = {3, 10, 5, 8, 2, 15};
for (int i = 0; i < 6; i++) insert(&h, vals[i]);
printf("Maximalwerte nacheinander entnehmen: ");
while (h.size > 0) {
printf("%d ", extractMax(&h));
}
printf("\n"); /* Ausgabe: 15 10 8 5 3 2 (absteigende Reihenfolge) */
return 0;
}
Anwendungsszenarien
| Szenario | Beschreibung |
|---|---|
| Prioritätswarteschlange | Der Heap ist die gebräuchlichste zugrunde liegende Implementierung einer Prioritätswarteschlange |
| Heap-Sortierung | O(n log n) In-Place-Sortieralgorithmus (ausführlich in Kapitel 18) |
| Top-K-Problem | Verwenden Sie einen Min-Heap, um die K größten Elemente zu verwalten |