Python heapq og tricks til max-heap
Brug heapq.heappush/heappop, negér værdier for at simulere en max-heap, og anvend heapq.nlargest/nsmallest til hurtige top-k-forespørgsler.
Python heapq og tricks til max-heap er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Oversigt over Pythons heapq-modul
Pythons heapq-modul leverer en min-heap, der er implementeret oven på en almindelig Python-liste. I modsætning til en dedikeret heap-klasse arbejder heapq direkte på eksisterende lister. Funktionerne i modulet er: heapify til at opbygge en heap i O(n), heappush til at tilføje et element i O(log n), heappop til at fjerne minimumselementet i O(log n) samt heappushpop / heapreplace til kombinerede effektivitetsforbedringer.
import heapq
# heapq operates on plain Python lists
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print('Heap array:', heap) # internal array (not sorted!)
print('Peek min:', heap[0]) # O(1) min access
print('Pop min:', heapq.heappop(heap)) # 1
print('Next min:', heap[0]) # 2
# heapify: turn any list into a heap in O(n)
data = [9, 4, 7, 1, 3, 6, 2]
heapq.heapify(data)
print('Heapified:', data, '| min:', data[0])Max-heap ved at negere værdier
Pythons heapq indeholder kun en min-heap. Hvis du vil simulere en max-heap, skal du negere alle værdier, før du indsætter dem, og negere dem igen, når du fjerner dem. Det virker, fordi heapen sorterer efter de gemte værdier, og negation vender sorteringsrækkefølgen. Husk altid at negere begge steder: negér før indsættelse, og negér efter fjernelse. Det er en almindelig fejl i jobsamtaler at glemme et af trinnene.
import heapq
max_heap = []
for val in [5, 1, 8, 3, 9, 2]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap internal:', max_heap) # all negated
# Pop in descending order:
results = []
while max_heap:
results.append(-heapq.heappop(max_heap)) # negate on pop
print('Sorted descending:', results) # [9, 8, 5, 3, 2, 1]
# Common pattern: top-k largest
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
heap = []
for x in data:
heapq.heappush(heap, -x)
print('Top', k, ':', [-heapq.heappop(heap) for _ in range(k)])heapq.nlargest og nsmallest
heapq.nlargest(k, iterable) og heapq.nsmallest(k, iterable) returnerer de k største eller mindste elementer. De har kompleksiteten O(n log k) og er mere effektive end fuld sortering (O(n log n)), når k er meget mindre end n. Internt bruger de en heap med størrelsen k. Når k er tæt på n, falder Python tilbage til fuld sortering. Brug dem til enkeltstående forespørgsler efter de k bedste elementer uden at vedligeholde en permanent heap.
import heapq
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 7]
# Top 3 largest:
print(heapq.nlargest(3, data)) # [9, 8, 7]
# Top 3 smallest:
print(heapq.nsmallest(3, data)) # [1, 1, 2]
# With a key function:
words = ['banana', 'apple', 'cherry', 'date', 'elderberry']
print(heapq.nlargest(2, words, key=len)) # ['elderberry', 'banana']
print(heapq.nsmallest(2, words, key=len)) # ['date', 'apple']
# Note: when k ~ n, use sorted() instead:
# sorted(data)[-k:] or sorted(data, reverse=True)[:k]Heap med tupler til komplekse nøgler
Når heap-elementer har brug for en brugerdefineret sammenligningsnøgle, skal du gemme dem som tupler (priority, data). Pythons heapq sammenligner tupler element for element, så prioriteterne sammenlignes først. Hvis prioriteterne er ens, sammenlignes det andet element — det kan give fejl, hvis dataene ikke kan sammenlignes. Det sikreste mønster er at inkludere en unik tæller som afgørelse ved lighed, så dataelementer aldrig sammenlignes direkte.
import heapq
import itertools
# Pattern: (priority, counter, item)
# Counter ensures unique tiebreaker, avoids comparing items
counter = itertools.count()
heap = []
def push_task(priority, task):
heapq.heappush(heap, (priority, next(counter), task))
push_task(3, 'low priority task')
push_task(1, 'high priority task')
push_task(2, 'medium priority task')
push_task(1, 'another high priority')
while heap:
pri, cnt, task = heapq.heappop(heap)
print(f'P{pri}: {task}')
# Output in priority order: P1, P1, P2, P3heapq.merge: Sammenfletning af sorterede itererbare objekter
heapq.merge(*iterables) sammenfletter dovent flere sorterede itererbare objekter til ét sorteret resultat uden at indlæse alle data i hukommelsen. Det svarer til en k-vejs sammenfletning ved hjælp af en min-heap med størrelsen k og bruges i eksterne sorteringsalgoritmer. Funktionen returnerer en iterator, så elementerne produceres ét ad gangen — ideelt til store datasæt eller scenarier med datastrømning.
import heapq
# Merge multiple sorted lists efficiently
sorted_lists = [
[1, 5, 9],
[2, 6, 8],
[3, 4, 7]
]
# heapq.merge takes sorted iterables and returns a merged sorted iterator
merged = list(heapq.merge(*sorted_lists))
print('Merged:', merged) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
# The k-way merge manually (educational version):
def merge_k_sorted(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
heapq.heappush(heap, (lists[list_idx][elem_idx+1], list_idx, elem_idx+1))
return result
print('Manual k-way:', merge_k_sorted(sorted_lists))Mønster til udskudt sletning i heaps
Når du skal fjerne vilkårlige elementer fra en heap, men ikke kender deres indeks, kan du bruge udskudt sletning: Markér elementerne som slettede i et separat sæt, og spring dem over, når du fjerner elementer. Det har en amortiseret kompleksitet på O(log n) og undgår besværet med at holde styr på indekser. Det er den almindelige tilgang i Dijkstras algoritme med duplikerede poster og simuleringer af opgaveplanlæggere.
import heapq
class LazyHeap:
def __init__(self):
self._heap = []
self._removed = set()
def push(self, task):
heapq.heappush(self._heap, task)
def remove(self, task):
self._removed.add(task) # mark as removed
def pop(self):
while self._heap:
task = heapq.heappop(self._heap)
if task not in self._removed:
return task
return None
lh = LazyHeap()
for t in [5, 1, 8, 3, 2]:
lh.push(t)
lh.remove(1) # 'delete' 1 lazily
lh.remove(8) # 'delete' 8 lazily
results = [lh.pop() for _ in range(3)]
print(results) # [2, 3, 5] -- 1 and 8 skippedDet k'te største element i en datastrøm
Det k'te største element i en datastrøm (LeetCode #703) vedligeholder en min-heap med størrelsen k. Heapens rod er altid det k'te største element, der er set indtil videre. Når et nyt tal ankommer: indsæt det, og fjern minimumselementet, hvis heapen overskrider størrelsen k. Roden er altid det k'te største element, fordi der præcis er k-1 elementer i heapen, der er større end det.
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = []
for num in nums:
self.add(num)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # remove smallest
return self.heap[0] # kth largest = root of min-heap
# k=3, initial=[4,5,8,2]
kl = KthLargest(3, [4, 5, 8, 2])
print(kl.add(3)) # 4 (top 3: 8,5,4 -- kth=4)
print(kl.add(5)) # 5 (top 3: 8,5,5 -- kth=5)
print(kl.add(10)) # 5 (top 3: 10,8,5 -- kth=5)
print(kl.add(9)) # 8 (top 3: 10,9,8 -- kth=8)Find K par med den mindste sum
Find K par med de mindste summer (LeetCode #373) bruger en min-heap til at generere par i rækkefølge. Start med alle par (nums1[0], nums2[j]) for hvert j. Fjern minimumselementet, og indsæt for det fjernede par (nums1[i], nums2[j]) (nums1[i+1], nums2[j]) — den næste kandidat fra den samme nums2-kolonne. Dette er et almindeligt mønster til generering af ordnede par eller produkter med en heap.
import heapq
def k_smallest_pairs(nums1, nums2, k):
if not nums1 or not nums2:
return []
heap = []
# Initialize with pairs (nums1[0], nums2[j])
for j in range(min(k, len(nums2))):
heapq.heappush(heap, (nums1[0] + nums2[j], 0, j))
result = []
while heap and len(result) < k:
total, i, j = heapq.heappop(heap)
result.append([nums1[i], nums2[j]])
if i + 1 < len(nums1):
heapq.heappush(heap, (nums1[i+1] + nums2[j], i+1, j))
return result
print(k_smallest_pairs([1,7,11], [2,4,6], 3))
# [[1,2], [1,4], [1,6]]Opgaveplanlægger med en max-heap
Opgaveplanlægger (LeetCode #621) spørger efter den minimale tid til at planlægge n opgaver med en køleperiode på n intervaller mellem ens opgaver. Brug en max-heap med opgavernes hyppigheder: Vælg ved hvert tidsskridt den hyppigst forekommende tilgængelige opgave, mindsk dens antal, og sæt den på køl. Behandl k=n+1 opgaver pr. cyklus, eller udfyld med inaktiv tid. Denne grådige tilgang med en max-heap giver det optimale svar.
import heapq
from collections import Counter
def least_interval(tasks, n):
freq = Counter(tasks)
heap = [-f for f in freq.values()] # max-heap (negated)
heapq.heapify(heap)
time = 0
while heap:
cycle = n + 1
temp = []
for _ in range(cycle):
if heap:
temp.append(heapq.heappop(heap))
for f in temp:
if f + 1 < 0: # still tasks remaining
heapq.heappush(heap, f + 1)
# Add full cycle or remaining tasks if queue empty
time += cycle if heap else len(temp)
return time
print(least_interval(['A','A','A','B','B','B'], 2)) # 8
print(least_interval(['A','A','A','B','B','B'], 0)) # 6Heap i Dijkstras algoritme
Prioritetskøen i Dijkstras algoritme implementeres med en min-heap. Gem tupler (distance, node), og behandl altid den nærmeste ubesøgte knude først. Når du fjerner en knude med en afstand, der er større end dens aktuelt kendte korteste sti, skal du springe den over, da det er en forældet post fra udskudt sletning. Det eliminerer behovet for en decrease-key-operation og holder implementeringen enkel, samtidig med at kompleksiteten O((V + E) log V) bevares.
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # stale entry, skip
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = {
'A': [('B', 4), ('C', 1)],
'B': [('D', 1)],
'C': [('B', 2), ('D', 5)],
'D': []
}
print(dijkstra(graph, 'A')) # {'A':0,'B':3,'C':1,'D':4}Omorganisering af en streng med en max-heap
Omorganisering af en streng (LeetCode #767) beder dig om at omarrangere en streng, så ingen to tegn ved siden af hinanden er ens. Brug en max-heap med (-frequency, char). Fjern det tegn, der forekommer hyppigst, ved hvert trin. Hvis det foregående tegn er det samme som det hyppigste tegn, skal du i stedet fjerne det næsthyppigste. Denne grådige tilgang sikrer, at det mest begrænsede tegn placeres så tidligt som muligt.
import heapq
from collections import Counter
def reorganize_string(s):
freq = Counter(s)
heap = [(-f, c) for c, f in freq.items()]
heapq.heapify(heap)
result = []
prev_freq, prev_char = 0, ''
while heap:
freq, char = heapq.heappop(heap)
result.append(char)
# Push back the previous character if still remaining
if prev_freq < 0:
heapq.heappush(heap, (prev_freq, prev_char))
prev_freq, prev_char = freq + 1, char # decrement freq (less negative)
result_str = ''.join(result)
# Verify no adjacent duplicates
return result_str if len(result_str) == len(s) else ''
print(reorganize_string('aab')) # 'aba'
print(reorganize_string('aaab')) # '' (impossible)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: Pythons heapq-modul og dets API, herunder heapify, heappush, heappop, nlargest, nsmallest og merge, simulering af max-heap ved at negere værdier samt almindelige heap-mønstre til jobsamtaler, herunder løbende forespørgsler efter de k bedste elementer, det k'te største element i en datastrøm, opgaveplanlæggeren og Dijkstra. I næste lektion tager vi fat på medianen fra en datastrøm og k-vejs sammenfletning.
Lær Forberedelse til kodeinterviews 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
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Python heapq og tricks til max-heap” gratis?
Ja — hele teksten til “Python heapq og tricks til max-heap” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Python heapq og tricks til max-heap”?
Brug heapq.heappush/heappop, negér værdier for at simulere en max-heap, og anvend heapq.nlargest/nsmallest til hurtige top-k-forespørgsler. Du øver dig i Forberedelse til kodeinterviews 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å Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews 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 3 af 4.
Hvor lang tid tager lektionen “Python heapq og tricks til max-heap”?
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 Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-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