0Pricing
Coding Interview Prep · Lektion

Heapify, Push und Pop von Grund auf

Implementieren Sie Heapify-up für push und Heapify-down für pop und erstellen Sie anschließend mit Floyds Algorithmus aus einem unsortierten Array in O(n) einen Heap.

Heapify, Push und Pop von Grund auf ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 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.

MinHeap-Klasse erstellen

Die Implementierung eines Heaps von Grund auf zeigt, dass Sie die zugrunde liegenden Mechanismen beherrschen, und wird gelegentlich in Senior-Interviews verlangt. Eine MinHeap-Klasse kapselt ein Array und stellt die Operationen push, pop, peek und size bereit. Intern erhält sie die Heap-Eigenschaft aufrecht, indem sie nach Push Sift-up und nach Pop Sift-down aufruft. Wenn Sie diese Implementierung verstehen, wird Pythons Modul heapq vollständig durchschaubar.

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self):
        if len(self._data) == 1:
            return self._data.pop()
        min_val = self._data[0]
        self._data[0] = self._data.pop()  # move last to root
        self._sift_down(0)
        return min_val

    def peek(self):
        return self._data[0] if self._data else None

    def size(self):
        return len(self._data)

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

print('MinHeap class skeleton defined')

Sift-up implementieren

Sift-up vergleicht einen Knoten mit seinem Elternknoten und tauscht ihn nach oben, solange die Heap-Eigenschaft (parent <= child beim Min-Heap) verletzt ist. Entscheidend ist, dass sich das neu eingefügte Element am Ende befindet und an seine richtige Position nach oben wandert. Die while-Schleife wird höchstens floor(log n)-mal ausgeführt – entsprechend der Höhe des Baums. Weisen Sie bei jedem Schritt i = parent zu, um weiter nach oben zu gehen.

class MinHeap:
    def __init__(self):
        self._data = []

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

    def _sift_up(self, i):
        while i > 0:
            p = self._parent(i)
            if self._data[p] > self._data[i]:  # parent > child: swap
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else:
                break  # heap property satisfied

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

h = MinHeap()
for v in [5, 3, 8, 1, 4]:
    h.push(v)
print(h._data)  # valid min-heap

Sift-down implementieren

Sift-down bewegt einen Knoten nach unten, indem er ihn wiederholt mit seinem kleinsten Kind tauscht (beim Min-Heap), bis kein Kind mehr kleiner ist oder der Knoten ein Blatt erreicht. Vergleichen Sie immer beide Kinder und tauschen Sie mit dem kleineren, um die Heap-Eigenschaft aufrechtzuerhalten. Denken Sie daran, vor dem Vergleichen der Werte zu prüfen, ob die Indizes der Kinder innerhalb der Grenzen liegen.

def _sift_down(data, i):
    n = len(data)
    while True:
        smallest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and data[l] < data[smallest]:
            smallest = l
        if r < n and data[r] < data[smallest]:
            smallest = r
        if smallest == i:
            break  # already the smallest among i, l, r
        data[i], data[smallest] = data[smallest], data[i]
        i = smallest

# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap)  # 1 should reach top, 10 sink

MinHeap um Pop ergänzen

Die Pop-Operation entfernt die Wurzel und gibt sie zurück (beim Min-Heap das Minimum). Um die Form des vollständigen Binärbaums zu erhalten, verschieben Sie das letzte Element an die Position der Wurzel und führen Sie anschließend Sift-down aus. So entstehen keine Lücken im Array und die Darstellung bleibt gültig. Sonderfall: Wenn nur ein Element übrig ist, entfernen Sie es und geben Sie es direkt zurück, ohne Sift-down auszuführen.

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] > self._data[i]:
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()  # last -> root
        i, n = 0, len(self._data)
        while True:
            s, l, r = i, 2*i+1, 2*i+2
            if l < n and self._data[l] < self._data[s]: s = l
            if r < n and self._data[r] < self._data[s]: s = r
            if s == i: break
            self._data[i], self._data[s] = self._data[s], self._data[i]
            i = s
        return result

h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [1,2,3,4,5,8] sorted

Floyds Heapify-Algorithmus

Floyds Algorithmus erstellt aus einem unsortierten Array in O(n) einen Min-Heap, indem er Sift-down für jeden Nicht-Blattknoten aufruft. Dabei beginnt er beim letzten inneren Knoten (n//2 - 1) und arbeitet sich zur Wurzel vor. Blätter sind bereits triviale, gültige Heaps mit einem Element. Die Laufzeit O(n) ergibt sich daraus, dass sich die meisten Knoten nahe am unteren Ende des Baums befinden und nur eine kurze Strecke nach unten verschoben werden müssen.

def heapify(arr):
    n = len(arr)
    # Start from last non-leaf: index n//2 - 1
    # Work backward to root (index 0)
    for i in range(n // 2 - 1, -1, -1):
        # Sift down node at index i
        j = i
        while True:
            s = j
            l, r = 2*j+1, 2*j+2
            if l < n and arr[l] < arr[s]: s = l
            if r < n and arr[r] < arr[s]: s = r
            if s == j: break
            arr[j], arr[s] = arr[s], arr[j]
            j = s
    return arr

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

Warum Floyds Algorithmus O(n) benötigt

Der Beweis für O(n): Der Baum enthält n/2^(k+1) Knoten auf Höhe k. Jeder Knoten auf Höhe k führt beim Sift-down höchstens k Vertauschungen durch. Gesamtaufwand = Summe über alle Höhen k: n/2^(k+1) * k. Diese geometrische Reihe konvergiert gegen O(n). Im Gegensatz dazu ist jedes naive Einfügen einzeln ein O(log n)-Vorgang, sodass n Einfügungen O(n log n) kosten. Floyds Algorithmus ist beim stapelweisen Erstellen strikt besser.

import time
import random

# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1))  # reverse sorted = worst case for push

# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
    j = i
    while True:
        s = j; l, r = 2*j+1, 2*j+2
        if l < n and data1[l] < data1[s]: s = l
        if r < n and data1[r] < data1[s]: s = r
        if s == j: break
        data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')

# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')

Heap-Push in eine bestehende Sammlung

Die Python-Funktionen heapq.heappushpop und heapq.heapreplace sind effiziente kombinierte Operationen. heappushpop(heap, item) fügt das neue Element ein und entfernt sofort das kleinste – effizienter als zwei separate Aufrufe. heapreplace(heap, item) entfernt das kleinste Element und fügt das neue in einem Durchlauf ein (das neue Element muss für eine korrekte Ausführung >= dem bisherigen Minimum sein). Diese Funktionen sind in Top-k-Streaming-Algorithmen nützlich.

import heapq

heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)

# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)

# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)

# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard pattern

MaxHeap von Grund auf implementieren

Ein MaxHeap kehrt den Vergleich um: Der Elternknoten muss größer oder gleich allen Nachkommen sein. Kehren Sie einfach den Vergleich in Sift-up und Sift-down um. Alternativ können Sie Werte in eine Klasse mit negierten Werten verpacken oder Ganzzahlen negieren, wie bei Pythons heapq. Die Implementierung von Grund auf zeigt, dass Min- und Max-Heaps identische Strukturen sind, bei denen sich nur der Vergleichsoperator ändert.

class MaxHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] < self._data[i]:  # FLIP: parent < child = violation
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()
        i, n = 0, len(self._data)
        while True:
            g = i; l, r = 2*i+1, 2*i+2
            if l < n and self._data[l] > self._data[g]: g = l  # FLIP
            if r < n and self._data[r] > self._data[g]: g = r  # FLIP
            if g == i: break
            self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
        return result

h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [8,5,4,3,2,1]

Beliebiges Element aus einem Heap löschen

Das Löschen eines beliebigen Elements (nicht der Wurzel) aus einem Heap benötigt O(log n), setzt aber voraus, dass Sie den Index des Elements kennen. Ersetzen Sie das Element durch das letzte Element, entfernen Sie das letzte Element und führen Sie anschließend entweder Sift-up oder Sift-down für das Ersatzelement aus (nur eine der beiden Richtungen verletzt die Heap-Eigenschaft). Diese Technik wird in Dijkstras Algorithmus mit Lazy Deletion und in Prioritätswarteschlangen verwendet, die Decrease-key-Operationen unterstützen.

def delete_at_index(heap, i):
    n = len(heap)
    heap[i] = heap[n - 1]
    heap.pop()
    if i >= len(heap):
        return  # deleted the last element
    # Try sift-up first
    p = (i - 1) // 2
    if i > 0 and heap[i] < heap[p]:
        while i > 0:
            p = (i - 1) // 2
            if heap[p] > heap[i]:
                heap[p], heap[i] = heap[i], heap[p]; i = p
            else: break
    else:  # sift down
        j = i; n2 = len(heap)
        while True:
            s = j; l, r = 2*j+1, 2*j+2
            if l < n2 and heap[l] < heap[s]: s = l
            if r < n2 and heap[r] < heap[s]: s = r
            if s == j: break
            heap[j], heap[s] = heap[s], heap[j]; j = s

heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2)  # delete element at index 2 (value=2)
print('After:', heap)  # 2 removed, heap still valid

Heap für die k häufigsten Elemente

Die k häufigsten Elemente (LeetCode #347) verwenden einen Min-Heap der Größe k. Verwalten Sie einen Min-Heap, in dem jeder Eintrag aus (frequency, element) besteht. Verarbeiten Sie jedes eindeutige Element: Hat der Heap weniger als k Elemente, fügen Sie es ein; andernfalls entfernen Sie das Minimum des Heaps und fügen das neue Element ein, wenn dessen Häufigkeit das Minimum des Heaps übersteigt. Der fertige Heap enthält die k häufigsten Elemente in O(n log k) Zeit.

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    # Min-heap of (frequency, num)
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)  # remove least frequent
    return [num for freq, num in heap]

print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]

Heap-Anwendungen beim Scheduling

Über die Wettbewerbsprogrammierung hinaus bilden Heaps die Grundlage für Scheduling-Systeme in der Praxis. Aufgabenplaner von Betriebssystemen verwenden eine Prioritätswarteschlange (Heap), um immer den bereiten Prozess mit der höchsten Priorität auszuführen. Ereignisgesteuerte Simulationen verarbeiten Ereignisse zeitlich geordnet mithilfe eines Min-Heaps, dessen Schlüssel die Ereigniszeit ist. Netzwerk-Paketplaner priorisieren den Datenverkehr anhand der Quality-of-Service-Klasse. Das Verständnis von Heaps vermittelt Ihnen ein mentales Modell für all diese Systeme und kommt in Systemdesign-Interviews zu Warteschlangen und Scheduling ganz natürlich zur Sprache.

import heapq

# Simple event-driven simulation using a heap
events = []  # (time, event_description)

def schedule(time, event):
    heapq.heappush(events, (time, event))

def process_next():
    time, event = heapq.heappop(events)
    print(f't={time}: {event}')
    return time, event

# Schedule events out of order:
schedule(10, 'Send email')
schedule(3,  'Open app')
schedule(7,  'Process request')
schedule(1,  'Start server')

# Process in time order:
while events:
    process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time order

Schnelltest

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep, die in dieser Lektion behandelt wurden.

Zusammenfassung der Lektion

In dieser Lektion haben Sie Folgendes gelernt: MinHeap und MaxHeap von Grund auf mit Sift-up und Sift-down, Floyds O(n)-heapify-Algorithmus und warum er schneller ist als das schrittweise Einfügen mit O(n log n) sowie praktische Anwendungen wie die k häufigsten Elemente und das Löschen an einem Index. Als Nächstes erkunden Sie Pythons heapq-Modul und Tricks für Max-Heaps.

Häufig gestellte Fragen

Ist die Lektion „Heapify, Push und Pop von Grund auf“ kostenlos?

Ja — der vollständige Text von „Heapify, Push und Pop von Grund auf“ 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 „Heapify, Push und Pop von Grund auf“?

Implementieren Sie Heapify-up für push und Heapify-down für pop und erstellen Sie anschließend mit Floyds Algorithmus aus einem unsortierten Array in O(n) einen Heap. 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 2 von 4.

Wie lange dauert die Lektion „Heapify, Push und Pop von Grund auf“?

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