Heap (Binärer Heap)

Q: Dauert der Aufbau eines Heaps aus n Elementen O(n log n)?

Nicht, wenn Sie ihn auf einmal aufbauen. Das Einfügen von `n` Elementen nacheinander ist `O(n log n)`, aber das Bottom-up-`heapify`, das vom letzten Elternknoten bis zur Wurzel absteigt, läuft insgesamt in `O(n)`, weil die meisten Knoten nahe am Boden liegen und nur eine kurze Strecke absteigen.

Zuletzt aktualisiert 1. Juli 2026

Ein binärer Heap ist ein vollständiger Binärbaum, der den kleinsten (Min-Heap) oder größten (Max-Heap) Wert an der Wurzel hält. Diese Visualisierung ist ein Min-Heap: Jeder Elternknoten ist kleiner oder gleich seinen Kindern. Um einen Wert hinzuzufügen, hängt man ihn an die nächste freie Position an und lässt ihn dann "aufsteigen", indem man ihn mit seinem Elternknoten tauscht, solange er kleiner ist, bis die Heap-Eigenschaft wieder erfüllt ist. Drücken Sie oben auf Wiedergabe, um zu sehen, wie jeder neue Wert an seinen Platz aufsteigt.

Da ein Heap ein vollständiger Baum ist, wird er kompakt in einem Array gespeichert: Die Kinder von Knoten i liegen bei 2i+1 und 2i+2. Einfügen und Entfernen des Minimums sind O(log n) (ein Pfad von der Wurzel zu einem Blatt), während das Ablesen des Minimums O(1) ist - genau das, was eine Prioritätswarteschlange braucht.

Zeit- und Speicherkomplexität

Operation	Komplexität	Hinweise
Min/Max ansehen	O(1)	Es ist immer die Wurzel
Einfügen (push)	O(log n)	Entlang eines Pfads aufsteigen
Min/Max entfernen	O(log n)	Entlang eines Pfads absteigen
Heap aufbauen	O(n)	Alles auf einmal heapify
Speicher	O(n)	Array-basiert, keine Zeiger

Schritt für Schritt (push)

Schritt	Was passiert
1	Hängen Sie den neuen Wert am Ende an (das nächste freie Blatt).
2	Vergleichen Sie ihn mit seinem Elternknoten.
3	Ist er kleiner (Min-Heap), tauschen Sie ihn nach oben.
4	Wiederholen, bis er nicht mehr kleiner als sein Elternknoten ist oder die Wurzel erreicht.

Durchgerechnetes Beispiel

Aufbau eines Min-Heaps durch Einfügen von [5, 3, 8, 1, 4] Wert für Wert:

Push	Array nach dem Aufsteigen	Aktion
`5`	`[5]`	Der erste Wert wird zur Wurzel.
`3`	`[3, 5]`	`3` < Elternknoten `5`, steigt daher bis zur Wurzel auf.
`8`	`[3, 5, 8]`	`8` > Elternknoten `5`, bleibt daher ein Blatt.
`1`	`[1, 3, 8, 5]`	`1` < Elternknoten `5`, Tausch; dann `1` < Elternknoten `3`, steigt bis zur Wurzel auf.
`4`	`[1, 3, 8, 5, 4]`	`4` > Elternknoten `3`, bleibt daher; das Minimum `1` verbleibt an der Wurzel.

Wann man einen Heap verwendet

Verwenden, wenn	Vermeiden, wenn
Sie wiederholt das kleinste oder größte Element aus einer sich ändernden Menge brauchen.	Sie beliebige Werte suchen müssen, nicht nur den Extremwert - verwenden Sie einen BST oder ein Hash-Set.
Sie eine Prioritätswarteschlange für Dijkstra, A* oder einen Scheduler implementieren.	Sie die Daten jederzeit vollständig sortiert halten müssen.
Sie Einfügen und Entfernen des Minimums in `O(log n)` mit kompakter Array-Anordnung wollen.	Sie ein schnelles Nachschlagen oder Entfernen eines bestimmten (nicht Wurzel-) Elements brauchen.
Sie einen Strom von Elementen zusammenführen und nach Priorität herausziehen müssen.	Der Datensatz winzig ist und ein linearer Durchlauf einfacher und schnell genug ist.

Heap (Priority Queue)-Code

Eine saubere, lauffähige Heap (Priority Queue)-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.

Heap (Priority Queue)-Code in PythonPython
1class MinHeap:2    def __init__(self):3        self.data = []4
5    def push(self, value):6        # Append at the end, then bubble up to restore order7        self.data.append(value)8        i = len(self.data) - 19        while i > 0:10            parent = (i - 1) // 211            if self.data[parent] <= self.data[i]:12                break13            self.data[i], self.data[parent] = self.data[parent], self.data[i]14            i = parent15
16    def pop(self):17        # Move the last leaf to the root, then sift it down18        top = self.data[0]19        last = self.data.pop()20        if self.data:21            self.data[0] = last22            self._sift_down(0)23        return top24
25    def _sift_down(self, i):26        n = len(self.data)27        while True:28            smallest = i29            left, right = 2 * i + 1, 2 * i + 230            if left < n and self.data[left] < self.data[smallest]:31                smallest = left32            if right < n and self.data[right] < self.data[smallest]:33                smallest = right34            if smallest == i:35                return36            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37            i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42    heap.push(value)43
44print("Heap array:     ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])
Führe diesen Code im Python-Playground aus

Heap (Priority Queue)-Code in JavaScriptJavaScript
1class MinHeap {2    constructor() {3        this.items = [];4    }5
6    push(value) {7        this.items.push(value);8        // Bubble the new value up while it is smaller than its parent9        let i = this.items.length - 1;10        while (i > 0) {11            const parent = Math.floor((i - 1) / 2);12            if (this.items[parent] <= this.items[i]) break;13            [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14            i = parent;15        }16    }17
18    pop() {19        const top = this.items[0];20        const last = this.items.pop();21        if (this.items.length > 0) {22            this.items[0] = last;23            this.sinkDown(0);24        }25        return top;26    }27
28    sinkDown(i) {29        const n = this.items.length;30        while (true) {31            let smallest = i;32            const left = 2 * i + 1;33            const right = 2 * i + 2;34            if (left < n && this.items[left] < this.items[smallest]) smallest = left;35            if (right < n && this.items[right] < this.items[smallest]) smallest = right;36            if (smallest === i) return;37            [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38            i = smallest;39        }40    }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));
Führe diesen Code im JavaScript-Playground aus

Heap (Priority Queue)-Code in JavaJava
1public class Main {2    static int[] heap = new int[32];3    static int size = 0;4
5    static void push(int value) {6        heap[size] = value;7        int i = size++;8        // Sift up while smaller than the parent9        while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10            swap(i, (i - 1) / 2);11            i = (i - 1) / 2;12        }13    }14
15    static int pop() {16        int min = heap[0];17        heap[0] = heap[--size];18        int i = 0;19        // Sift down: swap with the smaller child until in place20        while (true) {21            int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22            if (l < size && heap[l] < heap[smallest]) smallest = l;23            if (r < size && heap[r] < heap[smallest]) smallest = r;24            if (smallest == i) break;25            swap(i, smallest);26            i = smallest;27        }28        return min;29    }30
31    static void swap(int a, int b) {32        int tmp = heap[a];33        heap[a] = heap[b];34        heap[b] = tmp;35    }36
37    public static void main(String[] args) {38        int[] values = {9, 4, 7, 1, 8, 2};39        for (int v : values) push(v);40        System.out.print("Popped in order:");41        while (size > 0) System.out.print(" " + pop());42        System.out.println();43    }44}
Führe diesen Code im Java-Playground aus

Heap (Priority Queue)-Code in C++C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6    std::vector<int> data;7
8    void push(int value) {9        data.push_back(value);10        // Sift up until the parent is no larger11        size_t i = data.size() - 1;12        while (i > 0) {13            size_t parent = (i - 1) / 2;14            if (data[parent] <= data[i]) break;15            std::swap(data[parent], data[i]);16            i = parent;17        }18    }19
20    int pop() {21        int top = data[0];22        data[0] = data.back();23        data.pop_back();24        // Sift down: swap with the smaller child25        size_t i = 0;26        while (true) {27            size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28            if (l < data.size() && data[l] < data[smallest]) smallest = l;29            if (r < data.size() && data[r] < data[smallest]) smallest = r;30            if (smallest == i) break;31            std::swap(data[i], data[smallest]);32            i = smallest;33        }34        return top;35    }36
37    int peek() const { return data[0]; }38    bool empty() const { return data.empty(); }39};40
41int main() {42    MinHeap heap;43    for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44    std::cout << "Min: " << heap.peek() << "\n";45    std::cout << "Popped in order: ";46    while (!heap.empty()) std::cout << heap.pop() << " ";47    std::cout << "\n";48    return 0;49}
Führe diesen Code im C++-Playground aus

Heap (Priority Queue)-Code in CC
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9    // Sift up until the parent is no larger10    int i = heapSize++;11    heap[i] = value;12    while (i > 0) {13        int parent = (i - 1) / 2;14        if (heap[parent] <= heap[i]) break;15        int tmp = heap[parent];16        heap[parent] = heap[i];17        heap[i] = tmp;18        i = parent;19    }20}21
22int pop(void) {23    int top = heap[0];24    heap[0] = heap[--heapSize];25    // Sift down: swap with the smaller child26    int i = 0;27    while (1) {28        int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29        if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30        if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31        if (smallest == i) break;32        int tmp = heap[i];33        heap[i] = heap[smallest];34        heap[smallest] = tmp;35        i = smallest;36    }37    return top;38}39
40int main(void) {41    int values[] = {5, 3, 8, 1, 9, 2};42    for (int i = 0; i < 6; i++) push(values[i]);43    printf("Min: %d\n", heap[0]);44    printf("Popped in order: ");45    while (heapSize > 0) printf("%d ", pop());46    printf("\n");47    return 0;48}
Führe diesen Code im C-Playground aus

Heap-FAQ

Wofür wird ein Heap verwendet?

Heaps implementieren Prioritätswarteschlangen, die Dijkstras Kürzeste-Wege-Algorithmus, Task-Scheduler und Ereignissimulationen antreiben. Sie sind auch der Motor hinter Heapsort. Immer wenn Sie wiederholt das kleinste oder größte Element aus einer sich ändernden Menge brauchen, ist ein Heap das richtige Werkzeug.

Was ist der Unterschied zwischen einem Heap und einem binären Suchbaum?

Beide sind Binärbäume, aber ein BST hält eine vollständige Links-nach-rechts-Sortierung (die eine geordnete Suche ermöglicht), während ein Heap nur die Eltern-Kind-Beziehung garantiert (Min oder Max an der Wurzel). Ein Heap bietet O(1)-Zugriff auf den Extremwert; ein BST bietet O(log n)-Suche für jeden Wert.

Warum wird ein Heap in einem Array gespeichert?

Da ein Heap immer ein vollständiger Binärbaum ist, bilden seine Knoten sich perfekt auf Array-Indizes ab: Die Kinder von Index i liegen bei 2i+1 und 2i+2, der Elternknoten bei (i-1)/2. Das vermeidet das Speichern von Kind-Zeigern und bietet exzellente Cache-Leistung.

Ist ein Heap dasselbe wie ein sortiertes Array?

Nein. Ein Heap garantiert nur, dass jeder Elternknoten kleiner (Min-Heap) oder größer (Max-Heap) als seine Kinder ist, sodass Geschwister und Cousins in keiner bestimmten Reihenfolge stehen. Ein sortiertes Array ist vollständig geordnet, kostet aber O(n) beim Einfügen, während ein Heap in O(log n) einfügt und dennoch sofortigen Zugriff auf den Extremwert bietet.

Wann sollte ich einen Heap verwenden, statt ein Array einfach zu sortieren?

Greifen Sie zu einem Heap, wenn sich die Daten ständig ändern und Sie nur das aktuelle Minimum oder Maximum brauchen - Einfügen und Entnehmen kosten je O(log n), gegenüber dem erneuten Sortieren des gesamten Arrays. Wenn Sie einen statischen Datensatz haben und alle Elemente in Reihenfolge wollen, ist eine einzige O(n log n)-Sortierung einfacher und oft schneller.

Dauert der Aufbau eines Heaps aus n Elementen O(n log n)?

Nicht, wenn Sie ihn auf einmal aufbauen. Das Einfügen von n Elementen nacheinander ist O(n log n), aber das Bottom-up-heapify, das vom letzten Elternknoten bis zur Wurzel absteigt, läuft insgesamt in O(n), weil die meisten Knoten nahe am Boden liegen und nur eine kurze Strecke absteigen.