Median aus einem Datenstrom und K-Wege-Merge
Verwalten Sie zwei Heaps (Max-Heap der kleineren und Min-Heap der größeren Hälfte) für Medianaktualisierungen in O(log n) und führen Sie k sortierte Listen mit einem Heap zusammen.
Median aus einem Datenstrom und K-Wege-Merge ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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.
Problem: Median aus einem Datenstrom
Median aus einem Datenstrom finden (LeetCode #295) verlangt, zwei Operationen effizient zu unterstützen: addNum(num) zum Hinzufügen einer Zahl und findMedian() zum Zurückgeben des aktuellen Medians. Der Median einer Liste gerader Länge ist der Durchschnitt der beiden mittleren Werte. Eine brute-force sortierte Liste ermöglicht das Einfügen in O(n) und die Medianabfrage in O(1). Die optimale Lösung verwendet zwei Heaps für Einfügen in O(log n) und Medianabfragen in O(1).
import heapq
# Strategy: maintain two halves of the data
# max_heap: lower half (stores negated values for max behavior)
# min_heap: upper half
# Invariant: len(max_heap) == len(min_heap) or len(max_heap) == len(min_heap) + 1
# Invariant: max(max_heap) <= min(min_heap)
# Median:
# odd count: max_heap[0] (top of lower half)
# even count: average of tops of both halves
print('Two-heap strategy for O(log n) insert, O(1) median')Implementierung von MedianFinder mit zwei Heaps
Verwalten Sie einen Max-Heap für die untere Hälfte und einen Min-Heap für die obere Hälfte. Stellen Sie immer sicher, dass der Max-Heap gleich viele oder ein Element mehr als der Min-Heap enthält. Beim Hinzufügen einer Zahl fügen Sie sie zunächst in den Max-Heap ein. Balancieren Sie anschließend, indem Sie das oberste Element des Max-Heaps in den Min-Heap verschieben, wenn es größer als dessen Minimum ist, und gleichen Sie bei Bedarf die Größen an.
import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # max-heap (negated) for lower half
self.hi = [] # min-heap for upper half
def addNum(self, num):
heapq.heappush(self.lo, -num) # push to lower half
# Ensure max of lower <= min of upper
if self.hi and -self.lo[0] > self.hi[0]:
heapq.heappush(self.hi, -heapq.heappop(self.lo))
# Balance sizes: lo can have at most 1 more than hi
if len(self.lo) > len(self.hi) + 1:
heapq.heappush(self.hi, -heapq.heappop(self.lo))
elif len(self.hi) > len(self.lo):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def findMedian(self):
if len(self.lo) > len(self.hi):
return -self.lo[0] # odd count: top of lower half
return (-self.lo[0] + self.hi[0]) / 2
mf = MedianFinder()
for n in [1, 2, 3, 4, 5]: mf.addNum(n)
print(mf.findMedian()) # 3.0MedianFinder-Schritte nachvollziehen
Für die Erklärung der Lösung in einem Interview ist es entscheidend zu verstehen, warum die Invariante mit zwei Heaps erhalten bleibt. Sehen wir uns das Hinzufügen von [5, 15, 1, 3] Schritt für Schritt an. Balancieren Sie nach jeder Einfügung so, dass der untere Max-Heap die kleinere Hälfte enthält. Die Invariante stellt sicher, dass max(lo) <= min(hi) immer gilt, wodurch der Median am Anfang eines oder beider Heaps unmittelbar zugänglich ist.
import heapq
# Manual trace for [5, 15, 1, 3]:
# add 5: lo=[-5] hi=[] median=5
# add 15: lo=[-5] hi=[15] median=(5+15)/2=10
# add 1: lo=[-5,-1] hi=[15] median=5
# add 3: lo=[-5,-3,-1] hi=[15] -- lo too big
# -> lo=[-5,-3] hi=[1,15] -- wait, wrong direction
# Actually:
# add 1: push to lo -> lo=[-5,-1], then 1>lo? No, -lo[0]=5>15? No
# lo has 2, hi has 1: balance -> move lo top to hi
# lo=[-1], hi=[5,15]
# Median = (-lo[0] + hi[0])/2 = (1+5)/2 = 3
mf2 = MedianFinder()
for n, expected in [(5, 5.0), (15, 10.0), (1, 5.0), (3, 4.0)]:
mf2.addNum(n)
print(f'After adding {n}: median={mf2.findMedian()} (expected ~{expected})')Median des gleitenden Fensters
Der Median des gleitenden Fensters (LeetCode #480) ist eine schwierigere Variante: Finden Sie den Median jedes Fensters der Größe k, während es sich über das Array bewegt. Der Ansatz mit zwei Heaps wird um eine Menge für Lazy Deletion erweitert, um Elemente zu verarbeiten, die aus dem Fenster herausgleiten. Wenn ein Element das Fenster verlässt, markieren Sie es in der Löschmenge. Sobald es die Spitze eines der beiden Heaps erreicht, verwerfen Sie es.
import heapq
def median_sliding_window(nums, k):
lo = [] # max-heap (negated)
hi = [] # min-heap
removed = {}
result = []
def balance():
# Move valid tops to correct side
while lo and removed.get(-lo[0], 0) > 0:
removed[-lo[0]] -= 1; heapq.heappop(lo)
while hi and removed.get(hi[0], 0) > 0:
removed[hi[0]] -= 1; heapq.heappop(hi)
for i, num in enumerate(nums):
heapq.heappush(lo, -num)
heapq.heappush(hi, -heapq.heappop(lo))
if len(hi) > len(lo): heapq.heappush(lo, -heapq.heappop(hi))
if i >= k:
out = nums[i - k]
removed[out] = removed.get(out, 0) + 1
balance()
if len(lo) > len(hi): heapq.heappush(hi, -heapq.heappop(lo))
if i >= k - 1:
if len(lo) > len(hi): result.append(float(-lo[0]))
else: result.append((-lo[0] + hi[0]) / 2.0)
return result
print(median_sliding_window([1,3,-1,-3,5,3,6,7], 3)) # [1,-1,-1,3,5,6]k-Wege-Merge: Das Problem
K sortierte Listen zusammenführen (LeetCode #23) ist ein grundlegendes Problem mit Anwendungen in der externen Sortierung, bei Datenbankzusammenführungen und in verteilten Systemen. Gegeben sind k sortierte verkettete Listen mit insgesamt n Knoten, die zu einer sortierten Liste zusammengeführt werden sollen. Der naive Ansatz, jeweils zwei Listen zusammenzuführen, benötigt O(kn) oder mit Teile-und-herrsche-Verfahren O(n log k). Der Heap-Ansatz verarbeitet jeden Knoten genau einmal und benötigt pro Knoten O(log k): insgesamt O(n log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build a linked list from a Python list
def build_list(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
# Convert linked list to Python list for printing
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
print('K-way merge: O(n log k) using a min-heap of k heads')k-Wege-Merge mit einem Min-Heap
Initialisieren Sie den Heap mit dem ersten Knoten jeder Liste. Entfernen Sie in jedem Schritt das Minimum, fügen Sie es zum Ergebnis hinzu und fügen Sie den nächsten Knoten aus dieser Liste ein, sofern vorhanden. Der Heap enthält höchstens k Elemente – einen Kopfknoten pro aktiver Liste. Da insgesamt n Knoten verarbeitet werden und für jeden O(log k) Heap-Operationen anfallen, beträgt die Gesamtlaufzeit O(n log k) und der Speicherbedarf für den Heap O(k).
import heapq
def merge_k_lists(lists):
dummy = ListNode(0)
curr = dummy
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
lists = [
build_list([1, 4, 5]),
build_list([1, 3, 4]),
build_list([2, 6])
]
result = merge_k_lists(lists)
print(to_list(result)) # [1, 1, 2, 3, 4, 4, 5, 6]Kleinster Bereich, der K Listen abdeckt
Kleinster Bereich (LeetCode #632) findet den kleinsten Bereich [lo, hi], sodass mindestens ein Element aus jeder der k sortierten Listen innerhalb dieses Bereichs liegt. Verwenden Sie einen Min-Heap, der mit dem ersten Element jeder Liste initialisiert wird, und verfolgen Sie das aktuelle Maximum. Verkleinern Sie den Bereich, indem Sie stets die Liste mit dem aktuellen Minimum weiterführen. Beenden Sie den Vorgang, sobald eine Liste erschöpft ist.
import heapq
def smallest_range(nums):
heap = []
current_max = float('-inf')
for i, lst in enumerate(nums):
heapq.heappush(heap, (lst[0], i, 0))
current_max = max(current_max, lst[0])
best = [float('-inf'), float('inf')]
while heap:
current_min, list_idx, elem_idx = heapq.heappop(heap)
if current_max - current_min < best[1] - best[0]:
best = [current_min, current_max]
if elem_idx + 1 >= len(nums[list_idx]):
break # one list exhausted
next_val = nums[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
current_max = max(current_max, next_val)
return best
print(smallest_range([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]))
# [20, 24]K-kleinstes Element in einer Matrix
K-kleinstes Element in einer sortierten Matrix (LeetCode #378): eine n×n-Matrix, in der jede Zeile und Spalte sortiert ist. Finden Sie das k-kleinste Element. Betrachten Sie jede Zeile als sortierte Liste und verwenden Sie einen k-Wege-Merge mit einem Heap. Alternativ können Sie eine binäre Suche im Wertebereich durchführen. Der Heap-Ansatz benötigt O(k log n) und ist effizient, wenn k klein ist. Die binäre Suche benötigt O(n log(max-min)) und eignet sich besser für große k.
import heapq
def kth_smallest_matrix(matrix, k):
n = len(matrix)
heap = [(matrix[0][0], 0, 0)]
count = 0
visited = {(0, 0)}
while heap:
val, r, c = heapq.heappop(heap)
count += 1
if count == k:
return val
# Push right neighbor
if c + 1 < n and (r, c+1) not in visited:
heapq.heappush(heap, (matrix[r][c+1], r, c+1))
visited.add((r, c+1))
# Push bottom neighbor
if r + 1 < n and (r+1, c) not in visited:
heapq.heappush(heap, (matrix[r+1][c], r+1, c))
visited.add((r+1, c))
return -1
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kth_smallest_matrix(matrix, 8)) # 13Zwei Heaps für laufende Statistiken
Das Muster mit zwei Heaps lässt sich über den Median hinaus verallgemeinern. Sie können damit ein laufendes Quantil verwalten, beispielsweise das 25. Perzentil: Dimensionieren Sie den unteren Heap so, dass er p*n Elemente enthält, und den oberen Heap so, dass er (1-p)*n Elemente enthält. Balancieren Sie bei jedem hinzugefügten Element wie zuvor. Dieses Muster tritt in Problemen mit Streaming-Statistiken auf, bei denen effizientes Einfügen und Quantilabfragen gleichzeitig erforderlich sind.
import heapq
# Generalised two-heap for arbitrary quantile p
# lo contains floor(p * count) elements
# hi contains the remaining elements
class QuantileFinder:
def __init__(self, p):
self.p = p # quantile (e.g., 0.5 for median)
self.lo = [] # max-heap
self.hi = [] # min-heap
self.count = 0
def add(self, num):
self.count += 1
heapq.heappush(self.lo, -num)
heapq.heappush(self.hi, -heapq.heappop(self.lo))
# Target: lo should have floor(p * count) elements
target_lo = int(self.p * self.count)
while len(self.lo) < target_lo:
heapq.heappush(self.lo, -heapq.heappop(self.hi))
while len(self.lo) > target_lo:
heapq.heappush(self.hi, -heapq.heappop(self.lo))
def quantile(self):
return -self.lo[0] if self.lo else self.hi[0]
qf = QuantileFinder(0.5) # median
for n in [1, 2, 3, 4, 5, 6]: qf.add(n)
print(qf.quantile()) # 3 (median of 1-6)K nächstgelegene Punkte zum Ursprung finden
K nächstgelegene Punkte zum Ursprung (LeetCode #973) verwendet einen Max-Heap der Größe k. Fügen Sie die quadrierte Entfernung jedes Punkts ein, um sqrt zu vermeiden. Wenn der Heap die Größe k überschreitet, entfernen Sie den am weitesten entfernten Punkt. Die verbleibenden k Punkte sind die k nächstgelegenen. Dies benötigt O(n log k). Eine Alternative ist Quickselect mit einer durchschnittlichen Laufzeit von O(n), aber die Heap-Lösung ist einfacher korrekt zu implementieren und in einem Interview zu erklären.
import heapq
def k_closest(points, k):
heap = [] # max-heap via negation
for x, y in points:
dist_sq = x*x + y*y
heapq.heappush(heap, (-dist_sq, 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], [-1,-1]]
print(k_closest(points, 2))
# Two closest to origin: [0,1] (dist=1) and [-1,-1] (dist=2)
# Verify by distances:
for x, y in points:
print(f'({x},{y}): dist^2 = {x*x+y*y}')Zeit- und Speicheranalyse mit zwei Heaps
Der Ansatz mit zwei Heaps für den Median erreicht O(log n) pro addNum und O(1) pro findMedian. Der Speicherbedarf beträgt O(n), um alle Elemente zu speichern. Der k-Wege-Merge benötigt O(n log k) Zeit und O(k) Speicher für den Heap. Diese Lösungen sind nahezu optimal: Für den k-Wege-Merge lässt sich eine vergleichsbasierte untere Schranke von Omega(n log k) beweisen, wodurch der Heap-Ansatz asymptotisch optimal ist. Geben Sie diese Komplexitäten in Interviews immer klar an.
# Complexity summary for heap applications:
# Problem | Time per op | Space
# ----------------------|--------------|------
# MedianFinder.addNum | O(log n) | O(n)
# MedianFinder.find | O(1) | -
# Merge k sorted lists | O(n log k) | O(k)
# Kth smallest matrix | O(k log n) | O(n)
# K closest points | O(n log k) | O(k)
# Task scheduler | O(n log 26) | O(26)
# Kth largest stream | O(log k) | O(k)
# Sliding window median | O(n log k) | O(k)
print('Heap problems: identify k (heap size) vs n (input size)')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: den MedianFinder mit zwei Heaps mit Einfügen in O(log n) und Medianabfragen in O(1), den k-Wege-Merge mit einem Min-Heap in O(n log k) Zeit und mit O(k) Speicher sowie Erweiterungen wie den Median des gleitenden Fensters, den kleinsten Bereich und die k nächstgelegenen Punkte. Als Nächstes erkunden Sie Darstellungen von Graphen und die Vorbereitung ihrer Traversierung.
Lerne Coding Interview Prep mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 90
- Lektionen
- 360
Häufig gestellte Fragen
Ist die Lektion „Median aus einem Datenstrom und K-Wege-Merge“ kostenlos?
Ja — der vollständige Text von „Median aus einem Datenstrom und K-Wege-Merge“ 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 „Median aus einem Datenstrom und K-Wege-Merge“?
Verwalten Sie zwei Heaps (Max-Heap der kleineren und Min-Heap der größeren Hälfte) für Medianaktualisierungen in O(log n) und führen Sie k sortierte Listen mit einem Heap zusammen. 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 4 von 4.
Wie lange dauert die Lektion „Median aus einem Datenstrom und K-Wege-Merge“?
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
- Heap-Eigenschaft und Array-Darstellung
- Heapify, Push und Pop von Grund auf
- Python heapq und Tricks für Max-Heaps
- Median aus einem Datenstrom und K-Wege-Merge