0Pricing
Coding Interview Prep · Lektion

Heap-Eigenschaft und Array-Darstellung

Verstehen Sie die Struktur eines vollständigen Binärbaums in einem Array, leiten Sie Formeln für Eltern- und Kindindizes her und visualisieren Sie Sift-up- und Sift-down-Operationen.

Heap-Eigenschaft und Array-Darstellung ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was ist ein Heap?

Ein Heap ist ein spezialisierter vollständiger Binärbaum, der die Heap-Eigenschaft erfüllt: In einem Min-Heap ist jeder Elternknoten kleiner oder gleich seinen Kindern; in einem Max-Heap ist jeder Elternknoten größer oder gleich seinen Kindern. Diese Eigenschaft garantiert, dass das Minimum (beziehungsweise Maximum) immer an der Wurzel steht, und ermöglicht den Zugriff auf das Extremal-Element in O(1). Heaps sind die Datenstruktur hinter Prioritätswarteschlangen.

# Min-heap example:
#         1
#        / \
#       3   2
#      / \ / \
#     7  4 5  6
# Every parent <= its children
# Root (1) is always the minimum

# Max-heap example:
#         9
#        / \
#       7   8
#      / \ / \
#     3  4 5  6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')

Struktur eines vollständigen Binärbaums

Ein Heap wird als vollständiger Binärbaum gespeichert – alle Ebenen sind vollständig gefüllt, mit Ausnahme der möglicherweise letzten, die von links nach rechts gefüllt wird. Diese Struktur ermöglicht die elegante Array-Darstellung ohne ungenutzten Speicherplatz und ohne Zeiger. Die Eigenschaft der Vollständigkeit stellt sicher, dass die Höhe des Heaps immer floor(log₂ n) beträgt, und garantiert damit Push- und Pop-Operationen in O(log n).

# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))

# NOT complete (last level not left-filled):
#     1
#    / \
#   2   3
#        \
#         4  <- right child without left sibling

# Valid complete binary tree with 4 nodes:
#     1
#    / \
#   2   3
#  /
# 4
print('Complete BT: height = floor(log2(n)) always')

Array-Darstellung eines Heaps

Die Struktur des vollständigen Binärbaums ermöglicht es, einen Heap in einem einfachen Array ohne Zeiger zu speichern. Bei einem Knoten am Index i (beginnend bei Index 0) befindet sich sein Elternknoten an der Stelle (i-1) // 2, sein linkes Kind an der Stelle 2i+1 und sein rechtes Kind an der Stelle 2i+2. Diese Ganzzahlarithmetik ersetzt die Navigation über Zeiger und macht Heaps besonders cachefreundlich.

# Array representation (0-indexed):
# Index:  0  1  2  3  4  5  6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree:        1          (index 0)
#             / \         
#            3   2        (indices 1, 2)
#           / \ / \       
#          7  4 5  6      (indices 3,4,5,6)

# Index formulas (0-based):
def parent(i):      return (i - 1) // 2
def left_child(i):  return 2 * i + 1
def right_child(i): return 2 * i + 2

heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])

Sift-up: Heap nach dem Einfügen wiederherstellen

Sift-up (auch Bubble-up oder Heapify-up genannt) wird verwendet, nachdem ein neues Element am Ende des Heap-Arrays eingefügt wurde. Vergleichen Sie das neue Element mit seinem Elternknoten; ist die Heap-Eigenschaft verletzt, tauschen Sie beide und setzen Sie den Vorgang nach oben fort. Wiederholen Sie dies, bis sich das Element an der richtigen Position befindet oder die Wurzel erreicht. Dies läuft in O(log n), da die Höhe des Baums O(log n) beträgt.

def sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2  # parent index
        if heap[p] > heap[i]:  # min-heap: parent should be smaller
            heap[p], heap[i] = heap[i], heap[p]
            i = p
        else:
            break  # heap property restored

# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0)  # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap)  # 0 should bubble to root

Sift-down: Heap nach dem Entfernen wiederherstellen

Sift-down (Heapify-down) wird verwendet, nachdem die Wurzel entfernt wurde. Verschieben Sie das letzte Element an die Wurzel und bewegen Sie es anschließend nach unten, indem Sie es wiederholt mit dem kleineren Kind tauschen (beim Min-Heap), bis die Heap-Eigenschaft wiederhergestellt ist. Auch dies läuft in O(log n). Sift-up und Sift-down sind die Grundbausteine aller Heap-Operationen.

def sift_down(heap, i, n):
    while True:
        smallest = i
        l = 2 * i + 1  # left child
        r = 2 * i + 2  # right child
        if l < n and heap[l] < heap[smallest]:
            smallest = l
        if r < n and heap[r] < heap[smallest]:
            smallest = r
        if smallest == i:
            break  # already in correct position
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap)  # valid min-heap again

Heap aus einem Array erstellen: Floyds Algorithmus

Das naive Einfügen von n Elementen nacheinander benötigt O(n log n). Floyds Heapify-Algorithmus erstellt einen Heap in O(n), indem er Sift-down auf jeden Nicht-Blattknoten anwendet, beginnend beim letzten Nicht-Blattknoten (Index n//2 - 1) und rückwärts bis zur Wurzel. Blattknoten sind bereits triviale Heaps, daher müssen wir nur die inneren Knoten korrigieren – deshalb summiert sich der Gesamtaufwand zu O(n) statt O(n log n).

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node: index n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr)  # root should be 1

# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).

Heap-Sort mit dem Array-Heap

Heap-Sort läuft in O(n log n) mit O(1) zusätzlichem Speicherplatz. Phase 1: Erstellen Sie aus dem Array in O(n) einen Max-Heap. Phase 2: Extrahieren Sie wiederholt das Maximum, indem Sie die Wurzel mit dem letzten unsortierten Element tauschen und anschließend auf dem verkleinerten Heap Sift-down ausführen. Nach n Extraktionen ist das Array aufsteigend sortiert. Dieser In-Place-Algorithmus zeigt, wie die Array-Darstellung Sortieren ohne das Anlegen einer separaten Datenstruktur ermöglicht.

def sift_down_max(arr, i, n):
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(arr, i, n)
    # Extract elements one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # move max to end
        sift_down_max(arr, 0, end)

arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr)  # [1, 2, 3, 5, 7, 8, 9]

Min-Heap oder Max-Heap

Ein Min-Heap enthält das kleinste Element an der Wurzel; Pop liefert immer das Minimum. Ein Max-Heap enthält das größte Element an der Wurzel; Pop liefert immer das Maximum. Beide haben dieselbe Struktur und dieselben Operationen – nur die Vergleichsrichtung ändert sich. Das Python-Modul heapq implementiert ausschließlich einen Min-Heap. Um einen Max-Heap zu simulieren, müssen Sie daher die Werte negieren.

import heapq

# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap))  # 1

# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
    heapq.heappush(max_heap, -val)  # negate on push
print('Max-heap max:', -heapq.heappop(max_heap))  # 5 (negate on pop)

# For tuples: heapq sorts by first element
print(min_heap, max_heap)

Zusammenfassung der Heap-Operationskomplexität

Alle Heap-Operationen beruhen auf Sift-up und Sift-down, die beide O(log n) benötigen. Push: Anhängen + Sift-up = O(log n). Pop: Wurzel mit dem letzten Element tauschen + Sift-down = O(log n). Peek: Zugriff auf Index 0 = O(1). Heap erstellen: O(n) mithilfe von Floyds Algorithmus. Heap-Sort: O(n log n). Diese Komplexitäten machen Heaps zur idealen Struktur, wenn Sie wiederholt das Minimum oder Maximum einer dynamischen Sammlung benötigen.

# Heap complexity summary:
# Operation     | Time       | Space
# --------------|------------|-------
# Push          | O(log n)   | O(1)
# Pop (min/max) | O(log n)   | O(1)
# Peek          | O(1)       | O(1)
# Build from n  | O(n)       | O(1) in-place
# Heap sort     | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)

import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data))  # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data))  # [1, 2, 3]

Praktische Heap-Muster in Interviews

Heaps lösen eine ganze Familie von Interviewaufgaben nach einem gemeinsamen Muster: Sie verwalten eine Prioritätswarteschlange mit k Kandidaten, während Sie n Elemente als Stream durchlaufen. Die häufigsten Top-k-Elemente, die k nächstgelegenen Punkte zum Ursprung und ein Aufgabenplaner verwenden alle dieses Muster. Erkennen Sie es an der Formulierung: „Gegeben ist ein Stream mit n Elementen; halten Sie die k besten Elemente vor“ – dies erfordert immer einen Heap der Größe k und ergibt eine Gesamtlaufzeit von O(n log k).

import heapq

# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
    # Use max-heap (negate distance) of size k
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2))  # 2 closest to origin

Abwägung: Heap oder sortiertes Array

Wählen Sie einen Heap, wenn Sie nur wiederholt auf das Minimum oder Maximum zugreifen müssen und sich die Sammlung dynamisch verändert. Wählen Sie ein sortiertes Array, wenn Sie per Index auf Elemente zugreifen oder Bereichsabfragen durchführen müssen. Die Schwäche des Heaps ist die Suche nach beliebigen Elementen in O(n); seine Stärke sind Einfügen/Löschen in O(log n) und der Zugriff auf Minimum/Maximum in O(1). Ein sortiertes Array benötigt O(n) für das Einfügen, ermöglicht aber die Suche per Binärsuche in O(log n).

# Trade-off comparison:
# Structure     | insert  | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap      | O(logn) | O(logn)    | O(n)   | O(n)
# Sorted array  | O(n)    | O(n)       | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn)    | O(logn)| O(logn+k)
# Hash map      | O(1)    | O(1)       | O(1)   | O(n)

# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')

Schnelltest

Überprüfen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.

Zusammenfassung der Lektion

In dieser Lektion haben Sie Folgendes gelernt: die Heap-Eigenschaft und die Struktur des vollständigen Binärbaums, die Array-Darstellung mit Formeln für die Indizes von Elternknoten und Kindern sowie Sift-up und Sift-down als Grundbausteine aller Heap-Operationen einschließlich des Aufbaus in O(n) mit Floyds Algorithmus. Als Nächstes implementieren wir Heapify und untersuchen Pythons Modul heapq.

Häufig gestellte Fragen

Ist die Lektion „Heap-Eigenschaft und Array-Darstellung“ kostenlos?

Ja — der vollständige Text von „Heap-Eigenschaft und Array-Darstellung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Heap-Eigenschaft und Array-Darstellung“?

Verstehen Sie die Struktur eines vollständigen Binärbaums in einem Array, leiten Sie Formeln für Eltern- und Kindindizes her und visualisieren Sie Sift-up- und Sift-down-Operationen. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Coding Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.

Wie lange dauert die Lektion „Heap-Eigenschaft und Array-Darstellung“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Heap-Eigenschaft und Array-Darstellung
  2. Heapify, Push und Pop von Grund auf
  3. Python heapq und Tricks für Max-Heaps
  4. Median aus einem Datenstrom und K-Wege-Merge
← Zurück zu Coding Interview Prep