Heap

Die Priority Queue (Warteschlange mit Priorität). Im Drucker: Druckauftrag A (Chef, wichtig) kommt nach Druckauftrag B (Praktikant, unwichtig). Aber weil A wichtig ist, wird er vom Heap sofort nach ganz oben geschoben und als erstes gedruckt. In der Notaufnahme: Patient mit Herzinfarkt (Prio 1) überholt Patient mit Schnupfen (Prio 5), auch wenn er später kam.

1. Array-Repräsentation

Obwohl ein Heap ein Baum ist, speichert man ihn fast immer in einem simplen Array. Das spart Speicher (keine Pointer).

• Kind links: 2 * index + 1
• Kind rechts: 2 * index + 2 Mathematisch elegant.

2. Heapsort

Ein sehr effizienter Sortieralgorithmus (O(n log n)).

1. Wirf alle Zahlen in einen Heap.
2. Zieh n-mal die Wurzel (das Maximum) raus.
3. Fertig ist die sortierte Liste. Er braucht keinen extra Speicher (In-Place), ist aber oft etwas langsamer als Quicksort wegen schlechter Cache-Locality (er springt wild im Array herum).

1. Pointerlose Arrays & CPU Cache Thrashing

Warum ist ein Array-Heap in der Praxis einem Linked-Tree haushoch überlegen? Es liegt in der L1-Cache Locality moderner CPUs. Ein $N$-Baum verteilt die Nodes chaotisch im fernen RAM-Bereichen. Das Heap-Array [100, 19, 36, 17, ...] repräsentiert Hierarchien strikt mathematisch in nebeneinander liegenden Speicherzellen. Die Ironie bei massiven Heaps (> 1 GB) ist jedoch: Bei der Sink-Operation (Heapify-Down) wählt das Level-Puffern $i \rightarrow 2i$. Ein Sprung von Index 1 auf 2 ist harmlos. Aber Index 1 Million auf 2 Millionen zerbricht den 64-Byte Cache-Line Prefetch des Memory Controllers drastisch. Cache Thrashing eskaliert. Bei Data-Science-Giganten migriert man von standard Binären-Heaps auf d-ary Heaps (z. B. 4 Kinder pro Parent), was die Baustruktur erheblich in der Tiefe abflacht und Cache Misses halbiert.

2. Fibonacci Heaps und Amortisierte Analysen

Für extrem fortgeschrittene Graphen-Algorithmen (Dijkstra, Prim's Minimum Spanning Tree) ist das "Ändern einer Priorität" (Decrease-Key) die teuerste Hölle ($\mathcal{O}(\log n)$ beim Binär-Heap). Der Fibonacci Heap ist ein hyperkomplexer Wald abstrakter Heaptrees, der diese Zeit drückt. Ein Decrease-Key dauert dort unfassbare $O(1)$ amortisiert. Wie? Der Algorithmus ist extrem "faul" (Lazy Evaluation). Er reiht die abgeänderten Äste lose unaufgeräumt in Wurzel-Ketten an. Erst beim endgültigen Extrahieren des Minimums triggert ein enormer Consolidate-Schwall, der die losen Sub-Bäume in Binomial-Fibonacci-Rängen akribisch verlinkut. In der Systemprogrammierung vermeidet man Fibonacci oft trotzdem, da konstanter Overhead (Pointer) den theoretischen Asymptoten-Vorteil unter Linux physisch pulverisiert.

3. Memory Allocation Heaps (malloc vs. Free-Lists)

Der Begriff "Heap" beschreibt in C/C++ auch die unstrukturierte Area für dynamischen Memory (malloc). Historisch hieß er Heap, weil frühe OS-Memory-Manager Allokationsblöcke in echten Prioritäts-Heaps aufbauten, in der Nodes nach ihrer physischen Block-Größe saniert wurden ("Finde mir schnell ein großes Loch für meine Klasse!"). Heute nutzten Allocators (jemalloc, tcmalloc von Google) stark segregierte Bin/Free-List Caches (Slabs) pro Thread, die ohne Locks auskommen, und lassen das Binär-Heap-Design links liegen, auch wenn die Epoche des Begriffs unsterblich kleben blieb.