Median fra datastrøm og k-vejs-fletning
Vedligehold to heaps (max-heap for den lille halvdel og min-heap for den store halvdel) for medianopdateringer i O(log n), og flet k sorterede lister med en heap.
Median fra datastrøm og k-vejs-fletning er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Problemet med median fra en datastrøm
Find medianen fra en datastrøm (LeetCode #295) beder dig om at understøtte to operationer effektivt: addNum(num) til at tilføje et tal og findMedian() til at returnere den aktuelle median. Medianen i en liste med et lige antal elementer er gennemsnittet af de to midterste værdier. En sorteret liste med en direkte tilgang giver O(n) for indsættelse og O(1) for medianen. Den optimale løsning bruger to heaps til indsættelse i O(log n) og median i 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')Implementering af MedianFinder med to heaps
Vedligehold en max-heap for den nederste halvdel og en min-heap for den øverste halvdel. Sørg altid for, at max-heapen har samme størrelse som min-heapen eller ét element mere. Når du tilføjer et tal: indsæt det i max-heapen, og genopret derefter balancen ved at flytte toppen af max-heapen til min-heapen, hvis toppen er større end minimumselementet i min-heapen, og justér størrelserne efter behov.
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.0Gå trin for trin gennem MedianFinder
Det er afgørende at forstå, hvorfor invarianten for to heaps opretholdes, hvis du skal kunne forklare løsningen i en jobsamtale. Lad os gennemgå indsættelsen af [5, 15, 1, 3] trin for trin. Efter hver indsættelse skal du genoprette balancen, så den nederste max-heap indeholder den mindste halvdel. Invarianten sikrer, at max(lo) <= min(hi) altid gælder, så medianen er umiddelbart tilgængelig øverst i en af heapene eller i begge.
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 i et glidende vindue
Median i et glidende vindue (LeetCode #480) er en sværere variant: Find medianen for hvert vindue med størrelsen k, mens det glider hen over tabellen. Tilgangen med to heaps udvides med et sæt til udskudt sletning, så elementer, der glider ud af vinduet, kan håndteres. Når et element forlader vinduet, skal du markere det i slettesættet. Når det når toppen af en af heapene, skal du kassere det.
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]Problemet med k-vejs sammenfletning
Sammenflet K sorterede lister (LeetCode #23) er et grundlæggende problem med anvendelser inden for ekstern sortering, databasesammenfletning og distribuerede systemer. Du får k sorterede sammenkædede lister med i alt n knuder, som skal sammenflettes til én sorteret liste. Den naive tilgang, hvor du fletter to ad gangen, har kompleksiteten O(kn) eller O(n log k) med del-og-hersk. Heap-tilgangen behandler hver knude præcis én gang med O(log k) arbejde pr. knude: O(n log k) i alt.
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-vejs sammenfletning med en min-heap
Initialisér heapen med den første knude fra hver liste. Fjern minimumselementet ved hvert trin, tilføj det til resultatet, og indsæt den næste knude fra den pågældende liste, hvis der er en. Heapen indeholder altid højst k elementer — én første knude pr. aktiv liste. Da vi behandler n knuder i alt med O(log k)-heapoperationer for hver af dem, er den samlede tid O(n log k), og pladsforbruget er O(k) for heapen.
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]Mindste interval, der dækker K lister
Mindste interval (LeetCode #632) finder det mindste interval [lo, hi], så mindst ét element fra hver af de k sorterede lister ligger i intervallet. Brug en min-heap, der er initialiseret med det første element fra hver liste, og hold styr på den aktuelle maksimumsværdi. Gør intervallet mindre ved altid at gå videre i den liste, der har det aktuelle minimum. Stop, når en af listerne er udtømt.
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]Det k'te mindste element i en matrix
Det k'te mindste element i en sorteret matrix (LeetCode #378): en n×n-matrix, hvor hver række og kolonne er sorteret. Find det k'te mindste element. Betragt hver række som en sorteret liste, og brug k-vejs sammenfletning med en heap. Alternativt kan du bruge binær søgning i værdiintervallet. Heap-tilgangen har kompleksiteten O(k log n), hvilket er effektivt, når k er lille. Binær søgning har kompleksiteten O(n log(max-min)) og håndterer store k bedre.
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)) # 13To heaps til løbende statistik
Mønstret med to heaps kan generaliseres til mere end medianer. Du kan bruge det til at vedligeholde en løbende kvantil, f.eks. den 25. percentil: Dimensionér den nederste heap, så den indeholder p*n elementer, og den øverste heap, så den indeholder (1-p)*n elementer. Genopret balancen som før, hver gang et element tilføjes. Dette mønster optræder i problemer med statistik fra datastrømme, hvor du samtidig har brug for effektiv indsættelse og forespørgsler efter kvantiler.
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)Find K nærmeste punkter til origo
K nærmeste punkter til origo (LeetCode #973) bruger en max-heap med størrelsen k. Indsæt hvert punkts kvadrerede afstand for at undgå sqrt. Når heapen overskrider k elementer, skal du fjerne det fjerneste punkt. De resterende k punkter er de k nærmeste. Dette har kompleksiteten O(n log k). Et alternativ er quickselect med en gennemsnitlig kompleksitet på O(n), men heap-løsningen er enklere at implementere korrekt og forklare under en jobsamtale.
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}')Analyse af tid og plads for to heaps
Tilgangen med to heaps til medianer opnår O(log n) pr. addNum og O(1) pr. findMedian. Pladsforbruget er O(n), fordi alle elementer gemmes. K-vejs sammenfletning har tidskompleksiteten O(n log k) og pladsforbruget O(k) for heapen. Disse resultater er næsten optimale: Du kan bevise en nedre grænse på Omega(n log k) for k-vejs sammenfletning baseret på sammenligninger, hvilket viser, at heap-løsningen er asymptotisk optimal. Angiv altid disse kompleksiteter tydeligt i jobsamtaler.
# 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)')Hurtigt tjek
Test din forståelse af begreberne fra denne lektion i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du: MedianFinder med to heaps, der opnår indsættelse i O(log n) og median i O(1), k-vejs sammenfletning med en min-heap på O(n log k) tid og O(k) plads samt udvidelser som median i et glidende vindue, mindste interval og k nærmeste punkter. I næste lektion udforsker vi grafrepræsentationer og opsætning af gennemløb.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Median fra datastrøm og k-vejs-fletning” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Median fra datastrøm og k-vejs-fletning”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Median fra datastrøm og k-vejs-fletning”?
Vedligehold to heaps (max-heap for den lille halvdel og min-heap for den store halvdel) for medianopdateringer i O(log n), og flet k sorterede lister med en heap. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Median fra datastrøm og k-vejs-fletning”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Heap-egenskaben og arrayrepræsentation
- Heapify, push og pop fra bunden
- Python heapq og tricks til max-heap
- Median fra datastrøm og k-vejs-fletning