Median från dataström och k-vägs-sammanfogning
Underhåll två heapar, en max-heap för den mindre halvan och en min-heap för den större, för medianuppdateringar i O(log n) och sammanfoga k sorterade listor med en heap.
Median från dataström och k-vägs-sammanfogning är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Problemet med median från en dataström
Find Median from Data Stream (LeetCode #295) ber er effektivt stödja två operationer: addNum(num) för att lägga till ett tal och findMedian() för att returnera den aktuella medianen. Medianen för en lista med jämnt antal element är medelvärdet av de två mittersta värdena. En brute-force-lösning med en sorterad lista ger O(n) för insättning och O(1) för medianen. Den optimala lösningen använder två heapar för insättning på O(log n) och median på 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 av MedianFinder med två heapar
Underhåll en max-heap för den nedre halvan och en min-heap för den övre halvan. Säkerställ alltid att max-heapen har samma storlek som min-heapen eller ett element mer. När ett tal läggs till: lägg det i max-heapen, balansera sedan genom att flytta max-heapens topp till min-heapen om toppen överskrider min-heapens minimum, och balansera storlekarna igen vid 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.0Följ MedianFinder steg för steg
Att förstå varför invarianten för de två heaparna bibehålls är avgörande när ni förklarar lösningen i en intervju. Låt oss följa hur [5, 15, 1, 3] läggs till steg för steg. Efter varje insättning balanserar ni så att den nedre max-heapen innehåller den mindre halvan. Invarianten säkerställer att max(lo) <= min(hi) alltid gäller, vilket gör medianen direkt tillgänglig i toppen av en eller båda heaparna.
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 för glidande fönster
Sliding Window Median (LeetCode #480) är en svårare variant: hitta medianen för varje fönster med storleken k när det förflyttas över arrayen. Metoden med två heapar utökas med en mängd för lazy deletion för att hantera element som glider ut ur fönstret. När ett element lämnar fönstret markerar ni det i mängden för borttagning och slänger det när det når toppen av någon av heaparna.
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-vägsmerge: Problemet
Merge K Sorted Lists (LeetCode #23) är ett grundläggande problem med tillämpningar inom extern sortering, databassammanslagningar och distribuerade system. Givet k sorterade länkade listor med totalt n noder ska ni sammanfoga dem till en sorterad lista. Den naiva metoden, där två listor sammanfogas åt gången, har komplexiteten O(kn), eller O(n log k) med dela-och-härska. Heapmetoden behandlar varje nod exakt en gång med O(log k) arbete per nod: totalt 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-vägsmerge med en min-heap
Initiera heapen med den första noden i varje lista. Ta vid varje steg ut det minsta elementet, lägg till det i resultatet och lägg in nästa nod från den listan, om det finns någon. Heapen innehåller alltid högst k element — en första nod för varje aktiv lista. Eftersom ni behandlar totalt n noder med O(log k)-heapoperationer per nod blir den totala tidskomplexiteten O(n log k), och minnesåtgången för heapen är 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]Det minsta intervallet som täcker K listor
Smallest Range (LeetCode #632) hittar det minsta intervallet [lo, hi] sådant att minst ett element från var och en av de k sorterade listorna ligger inom intervallet. Använd en min-heap som initieras med det första elementet från varje lista och håll reda på det aktuella maximumet. Krymp intervallet genom att alltid gå vidare i listan med det aktuella minimumet. Avsluta när någon lista är uttömd.
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 minsta elementet i en matris
Kth Smallest Element in a Sorted Matrix (LeetCode #378): en n×n-matris där varje rad och kolumn är sorterad. Hitta det k:te minsta elementet. Betrakta varje rad som en sorterad lista och använd k-vägsmerge med en heap. Alternativt kan ni utföra binärsökning över värdeintervallet. Heapmetoden har komplexiteten O(k log n), vilket är effektivt när k är litet; binärsökning har komplexiteten O(n log(max-min)) och fungerar bättre för stora 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)) # 13Två heapar för löpande statistik
Mönstret med två heapar kan generaliseras bortom medianen. Ni kan använda det för att underhålla en löpande kvantil, exempelvis den 25:e percentilen: dimensionera den nedre heapen så att den innehåller p*n element och den övre heapen så att den innehåller (1-p)*n element. Balansera heaparna på samma sätt varje gång ett element läggs till. Detta mönster förekommer i problem om strömmande statistik där ni samtidigt behöver effektiv insättning och effektiva kvantilfrågor.
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)Hitta K punkter närmast origo
K Closest Points to Origin (LeetCode #973) använder en max-heap med storleken k. Lägg in varje punkts kvadrerade avstånd, för att undvika kvadratrot. När heapen överskrider storleken k tar ni bort den punkt som ligger längst bort. De återstående k punkterna är de k närmaste. Detta har komplexiteten O(n log k). Ett alternativ är quickselect med genomsnittlig komplexitet O(n), men heaplösningen är enklare att implementera korrekt och förklara under en intervju.
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}')Tids- och minnesanalys för två heapar
Metoden med två heapar för median ger O(log n) per addNum och O(1) per findMedian. Minnesåtgången är O(n) för att lagra alla element. K-vägsmerge har tidskomplexiteten O(n log k) och minnesåtgången O(k) för heapen. Dessa resultat är nära optimala: ni kan bevisa en jämförelsebaserad nedre gräns på Omega(n log k) för k-vägsmerge, vilket visar att heaplösningen är asymptotiskt optimal. Ange alltid dessa komplexiteter tydligt i intervjuer.
# 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)')Snabbtest
Testa era kunskaper om begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionens sammanfattning
I den här lektionen lärde ni er: MedianFinder med två heapar, som ger insättning på O(log n) och median på O(1), k-vägsmerge med en min-heap på O(n log k) tid och O(k) minne samt utökningar som median för glidande fönster, minsta intervall och k närmaste punkter. Härnäst utforskar vi grafrepresentationer och förberedelser för traversering.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Median från dataström och k-vägs-sammanfogning” gratis?
Ja – hela texten till ”Median från dataström och k-vägs-sammanfogning” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Median från dataström och k-vägs-sammanfogning”?
Underhåll två heapar, en max-heap för den mindre halvan och en min-heap för den större, för medianuppdateringar i O(log n) och sammanfoga k sorterade listor med en heap. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Median från dataström och k-vägs-sammanfogning”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Heap-egenskapen och arrayrepresentation
- Heapify, push och pop från grunden
- Pythons heapq och knep för max-heap
- Median från dataström och k-vägs-sammanfogning