Mediaan uit een datastroom en k-way merge
Onderhoud twee heaps (een max-heap van de kleinste helft en een min-heap van de grootste helft) voor mediaanupdates in O(log n) en voeg k gesorteerde lijsten samen met een heap.
Mediaan uit een datastroom en k-way merge is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Probleem: mediaan uit een gegevensstroom
Mediaan uit een gegevensstroom vinden (LeetCode #295) vraagt je om twee bewerkingen efficiënt te ondersteunen: addNum(num) om een getal toe te voegen en findMedian() om de huidige mediaan terug te geven. De mediaan van een lijst met een even lengte is het gemiddelde van de twee middelste waarden. Een gesorteerde lijst met brute kracht geeft O(n) voor invoegen en O(1) voor de mediaan. De optimale oplossing gebruikt twee heaps voor invoegen in O(log n) en de mediaan 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')Implementatie van MedianFinder met twee heaps
Houd een max-heap voor de onderste helft en een min-heap voor de bovenste helft bij. Zorg er altijd voor dat de max-heap evenveel elementen als, of één element meer dan, de min-heap bevat. Bij het toevoegen van een getal: voeg het toe aan de max-heap, breng daarna de verdeling in balans door de top van de max-heap naar de min-heap te verplaatsen als die top groter is dan het minimum van de min-heap, en herstel indien nodig de balans tussen de groottes.
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.0De stappen van MedianFinder doorlopen
Begrijpen waarom de invariant met twee heaps behouden blijft, is cruciaal om de oplossing in een sollicitatiegesprek uit te leggen. Laten we het toevoegen van [5, 15, 1, 3] stap voor stap doorlopen. Breng na elke invoeging de verdeling in balans, zodat de onderste max-heap de kleinere helft bevat. De invariant garandeert dat max(lo) <= min(hi) altijd geldt, waardoor de mediaan direct beschikbaar is aan de top van een of beide heaps.
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})')Mediaan van een schuivend venster
De mediaan van een schuivend venster (LeetCode #480) is een moeilijkere variant: vind de mediaan van elk venster met grootte k terwijl het over de array schuift. De aanpak met twee heaps wordt uitgebreid met een verzameling voor uitgestelde verwijdering om elementen te verwerken die uit het venster schuiven. Wanneer een element het venster verlaat, markeer je het in de verzameling voor verwijdering; wanneer het bovenaan een van beide heaps komt, verwijder je het.
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]Samenvoegen van k lijsten: het probleem
K gesorteerde lijsten samenvoegen (LeetCode #23) is een fundamenteel probleem met toepassingen bij extern sorteren, het samenvoegen van databases en gedistribueerde systemen. Gegeven k gesorteerde gekoppelde lijsten met in totaal n knopen, voeg je ze samen tot één gesorteerde lijst. De naïeve aanpak (twee lijsten tegelijk samenvoegen) heeft een complexiteit van O(kn), of O(n log k) met verdeel-en-heers. De heapbenadering verwerkt elke knoop precies één keer met O(log k) werk per knoop: in totaal 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')Samenvoegen in k richtingen met een min-heap
Initialiseer de heap met de eerste knoop van elke lijst. Verwijder bij elke stap het minimum, voeg het toe aan het resultaat en voeg de volgende knoop uit die lijst toe, als die bestaat. De heap bevat altijd hoogstens k elementen — één eerste element per actieve lijst. Omdat we in totaal n knopen verwerken met telkens O(log k) heapbewerkingen, is de totale tijd O(n log k) en is de ruimte O(k) voor de heap.
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]Kleinste bereik dat k lijsten omvat
Kleinste bereik (LeetCode #632) vindt het kleinste bereik [lo, hi] waarvoor ten minste één element uit elk van de k gesorteerde lijsten binnen het bereik ligt. Gebruik een min-heap die met het eerste element van elke lijst is geïnitialiseerd en houd het huidige maximum bij. Verklein het bereik door steeds de lijst met het huidige minimum vooruit te zetten. Stop zodra een lijst is uitgeput.
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]Het k-de kleinste element in een matrix
Het k-de kleinste element in een gesorteerde matrix (LeetCode #378): een n×n-matrix waarvan elke rij en kolom is gesorteerd. Vind het k-de kleinste element. Behandel elke rij als een gesorteerde lijst en gebruik een samenvoeging in k richtingen met een heap. Je kunt ook binair zoeken binnen het waardebereik. De heapbenadering is O(k log n) en efficiënt wanneer k klein is; binair zoeken is O(n log(max-min)) en werkt beter voor grote 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)) # 13Twee heaps voor doorlopende statistieken
Het patroon met twee heaps generaliseert verder dan de mediaan. Je kunt het gebruiken om een doorlopend kwantiel bij te houden, bijvoorbeeld het 25e percentiel: geef de onderste heap een grootte waarmee die p*n elementen bevat en de bovenste heap een grootte waarmee die (1-p)*n elementen bevat. Breng de verdeling telkens wanneer een element wordt toegevoegd opnieuw in balans zoals hiervoor. Dit patroon komt voor in statistiekproblemen met gegevensstromen waarin je tegelijk efficiënt elementen moet invoegen en kwantielen moet opvragen.
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 punten vinden die het dichtst bij de oorsprong liggen
K punten die het dichtst bij de oorsprong liggen (LeetCode #973) gebruikt een max-heap van grootte k. Voeg de gekwadrateerde afstand van elk punt toe om sqrt te vermijden. Wanneer de heap groter wordt dan k, verwijder je het verste punt. De overgebleven k punten zijn de k dichtstbijzijnde. Dit heeft een complexiteit van O(n log k). Een alternatief is quickselect met een gemiddelde complexiteit van O(n), maar de heapoplossing is eenvoudiger correct te implementeren en uit te leggen tijdens een sollicitatiegesprek.
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}')Twee heaps: analyse van tijd en ruimte
De aanpak met twee heaps voor de mediaan bereikt O(log n) per addNum en O(1) per findMedian. De ruimtecomplexiteit is O(n) om alle elementen op te slaan. De samenvoeging in k richtingen heeft een tijdcomplexiteit van O(n log k) en gebruikt O(k) ruimte voor de heap. Deze complexiteiten zijn bijna optimaal: je kunt een vergelijkingsgebaseerde ondergrens van Omega(n log k) voor samenvoeging in k richtingen bewijzen, waaruit blijkt dat de heapoplossing asymptotisch optimaal is. Vermeld deze complexiteiten altijd duidelijk tijdens sollicitatiegesprekken.
# 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)')Korte controle
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep in deze les.
Samenvatting van de les
In deze les heb je geleerd: MedianFinder met twee heaps voor invoegen in O(log n) en de mediaan in O(1), samenvoegen in k richtingen met een min-heap in O(n log k) tijd en O(k) ruimte, en uitbreidingen zoals de mediaan van een schuivend venster, het kleinste bereik en de k dichtstbijzijnde punten. Hierna bekijken we representaties van grafen en de voorbereiding voor het doorlopen ervan.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Mediaan uit een datastroom en k-way merge” gratis?
Ja — de volledige tekst van “Mediaan uit een datastroom en k-way merge” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Mediaan uit een datastroom en k-way merge”?
Onderhoud twee heaps (een max-heap van de kleinste helft en een min-heap van de grootste helft) voor mediaanupdates in O(log n) en voeg k gesorteerde lijsten samen met een heap. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Mediaan uit een datastroom en k-way merge”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Heap-eigenschap en arrayrepresentatie
- Heapify, push en pop vanaf nul
- Python heapq en trucs voor max-heaps
- Mediaan uit een datastroom en k-way merge