mysimulator.uk
🔍 Simulationen suchen…/
DE ▼
EnglishStandardУкраїнськаPolskiEspañolDeutsch日本語ItalianoPortuguês (BR)FrançaisالعربيةNederlands中文한국어हिन्दीTürkçeTiếng ViệtРусскийBahasa IndonesiaفارسیবাংলাไทยFilipinoKiswahiliاردوBahasa Melayuதமிழ்עבריתΕλληνικάਪੰਜਾਬੀአማርኛမြန်မာဘာသာខ្មែរქართულიनेपालीМонгол хэлՀայերենසිංහලລາວČeštinaRomânăMagyarБългарскиSvenskaDanskSuomiNorskSlovenčinaHrvatskiСрпскиSlovenščinaLietuviųLatviešuEestiÍslenskaShqipМакедонскиBosanskiMalti
Startseite▸Algorithmen & KI▸Binärer Heap — Prioritätswarteschlange

⛰️ Binärer Heap — Prioritätswarteschlange

Füge Werte in einen binären Min-Heap ein, der als Array gespeichert ist, und entnimm sie wieder. Beobachte, wie Sift-Up- und Sift-Down-Vertauschungen die Heap-Eigenschaft wiederherstellen, dargestellt sowohl als Baum als auch als zugrunde liegendes Array.

Algorithmen & KI2DMittel60 FPS
binary-heap ↗ Eigenständig öffnen

Über den binären Heap — Prioritätswarteschlange

Ein binärer Heap ist ein vollständiger Binärbaum — jede Ebene vollständig gefüllt außer möglicherweise der letzten, die von links nach rechts gefüllt wird — kompakt gespeichert in einem einfachen Array ohne Zeiger. Für jeden Index i lebt sein Elternteil bei ⌊(i−1)/2⌋ und seine Kinder bei 2i+1 und 2i+2, sodass die Baumstruktur allein durch das Indexierungsschema implizit gegeben ist. Ein Min-Heap wahrt die Heap-Eigenschaft: Der Wert jedes Elternteils ist kleiner oder gleich dem seiner beiden Kinder, wodurch garantiert das kleinste Element immer an Index 0 steht, auch wenn das Array selbst nicht vollständig sortiert ist. Das Einfügen eines Werts hängt ihn ans Ende an und lässt ihn nach oben sieben (Sift-Up), wobei er mit seinem Elternteil vertauscht wird, solange die Heap-Eigenschaft verletzt ist — eine O(log n)-Operation, begrenzt durch die Höhe des Baums. Das Entfernen des Minimums vertauscht die Wurzel mit dem letzten Element, verkleinert das Array und lässt dann die neue Wurzel nach unten sieben (Sift-Down) zu ihrem kleineren Kind, ebenfalls O(log n). Der Aufbau eines Heaps aus n unsortierten Werten durch Sift-Down vom letzten inneren Knoten aus läuft insgesamt in O(n), nicht O(n log n), weil die meisten Knoten nahe am unteren Ende liegen, wo Sift-Down nur wenig Arbeit verrichtet. Binäre Heaps liegen Prioritätswarteschlangen, Heapsort sowie den Algorithmen von Dijkstra und Prim zugrunde.

Häufig gestellte Fragen

Warum kann ein binärer Heap ohne Zeiger in einem Array gespeichert werden?

Weil es sich um einen vollständigen Binärbaum handelt, der Ebene für Ebene ohne Lücken gefüllt wird, lassen sich Elternknoten und Kinder eines Knotens direkt aus seinem Array-Index berechnen (Elternteil = ⌊(i−1)/2⌋, Kinder = 2i+1 und 2i+2). Das vermeidet den Speicheraufwand zeigerbasierter Baumknoten und bietet im Vergleich zu verketteten Strukturen eine hervorragende Cache-Lokalität.

Was ist der Unterschied in der Zeitkomplexität zwischen Sift-Up und Sift-Down?

Beide laufen im schlimmsten Fall in O(log n), da jedes nur einem einzigen Pfad von der Wurzel zu einem Blatt der Länge ⌊log₂ n⌋ folgt. Sift-Up macht höchstens einen Vergleich pro Ebene mit dem Elternteil, während Sift-Down bis zu zwei Vergleiche pro Ebene mit beiden Kindern macht, sodass Sift-Down trotz gleicher asymptotischer Schranke einen etwas größeren konstanten Faktor hat.

Warum ist der Aufbau eines Heaps aus n Elementen O(n) statt O(n log n)?

Floyds Heap-Aufbau-Algorithmus ruft Sift-Down nur bei inneren Knoten auf, beginnend beim letzten und aufsteigend bis zur Wurzel. Die meisten Knoten liegen nahe am unteren Ende des Baums, wo Sift-Down nur eine kurze Strecke zurücklegen kann; summiert man die Arbeit über alle Ebenen, ergibt sich eine geometrische Reihe, die gegen O(n) konvergiert, anders als die O(n log n)-Kosten beim einzelnen Einfügen von n Elementen.

Was ist der Unterschied zwischen einem Min-Heap und einem Max-Heap, und wie schneidet ein Heap im Vergleich zu einem balancierten BST für eine Prioritätswarteschlange ab?

Ein Min-Heap hält den kleinsten Wert an der Wurzel (Elternteil ≤ Kinder); ein Max-Heap hält den größten (Elternteil ≥ Kinder) — dieselben Algorithmen gelten mit umgekehrtem Vergleich. Verglichen mit einem balancierten binären Suchbaum bietet ein Heap dasselbe O(log n)-Einfügen und O(log n)-Extrahieren-des-Minimums, aber mit einer einfacheren arraybasierten Implementierung, ohne Rebalancierungslogik und mit O(1)-Blick auf das Minimum, während ein BST geordnete Traversierung und O(log n)-Suche für beliebige Schlüssel bietet, was ein Heap nicht unterstützt.

⚙ Unter der Haube

Füge Werte in einen binären Min-Heap ein, der als Array gespeichert ist, und entnimm sie wieder. Beobachte, wie Sift-Up- und Sift-Down-Vertauschungen die Heap-Eigenschaft wiederherstellen, dargestellt sowohl als Baum als auch als zugrunde liegendes Array.

data structurepriority queueheapsortingarray

2D · HTML5 Canvas 2D · Ziel: 60 FPS · läuft vollständig im Browser, keine Installation nötig

Was hast du gefunden?

Reproduktionsschritte hinzufügen (optional)