heapq di Python e trucchi per il max-heap
Usi heapq.heappush/heappop, neghi i valori per simulare un max-heap e applichi heapq.nlargest/nsmallest a rapide query top-k
heapq di Python e trucchi per il max-heap è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Panoramica del modulo heapq di Python
Il modulo heapq di Python fornisce un min-heap implementato sopra una normale lista Python. A differenza di una classe heap dedicata, heapq opera direttamente sulle liste esistenti. Le funzioni del modulo sono: heapify per costruire un heap in O(n), heappush per aggiungere un elemento in O(log n), heappop per rimuovere il minimo in O(log n) e heappushpop / heapreplace per combinare le operazioni in modo più efficiente.
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 tramite negazione dei valori
heapq di Python fornisce solo un min-heap. Per simulare un max-heap, neghi tutti i valori prima di inserirli e li neghi nuovamente quando li rimuove. Questo funziona perché l'heap ordina in base ai valori memorizzati e la negazione inverte l'ordinamento. Ricordi sempre di negare in entrambi i passaggi: prima dell'inserimento e dopo la rimozione. Dimenticare uno dei due passaggi è un errore comune nei colloqui tecnici.
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 e nsmallest
heapq.nlargest(k, iterable) e heapq.nsmallest(k, iterable) restituiscono i k elementi più grandi o più piccoli. Hanno complessità O(n log k), quindi sono più efficienti dell'ordinamento completo (O(n log n)) quando k è molto più piccolo di n. Internamente usano un heap di dimensione k. Quando k è vicino a n, Python ricorre all'ordinamento completo. Li utilizzi per query top-k eseguite una sola volta, senza mantenere un heap persistente.
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 con tuple per chiavi complesse
Quando gli elementi dell'heap richiedono una chiave di confronto personalizzata, li memorizzi come tuple (priority, data). heapq confronta le tuple elemento per elemento, quindi confronta prima le priorità. Se le priorità sono uguali, confronta il secondo elemento; ciò può causare errori se i dati non sono confrontabili. Il metodo più sicuro consiste nell'includere un contatore univoco come criterio di spareggio, così da evitare qualsiasi confronto diretto tra gli elementi dei dati.
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: unione di iterabili ordinati
heapq.merge(*iterables) unisce in modo lazy più iterabili ordinati in un unico output ordinato, senza caricare tutti i dati in memoria. Equivale a un'unione k-way che usa un min-heap di dimensione k ed è impiegato negli algoritmi di ordinamento esterno. Restituisce un iteratore, quindi gli elementi vengono prodotti uno alla volta: è ideale per dataset di grandi dimensioni o scenari di streaming.
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))Schema di cancellazione lazy per gli heap
Quando è necessario rimuovere elementi arbitrari da un heap senza conoscerne l'indice, utilizzi la cancellazione lazy: contrassegni gli elementi come cancellati in un set separato e poi li ignori durante la rimozione. La complessità ammortizzata è O(log n) e si evita la complessità di tenere traccia degli indici. È l'approccio standard nell'algoritmo di Dijkstra con voci duplicate e nelle simulazioni degli scheduler di attività.
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 skippedK-esimo elemento più grande in uno stream
Kth Largest Element in a Stream (LeetCode #703) mantiene un min-heap di dimensione k. La radice dell'heap è sempre il k-esimo elemento più grande osservato fino a quel momento. Quando arriva un nuovo numero: lo inserisca e, se l'heap supera la dimensione k, rimuova il minimo. La radice è sempre il k-esimo elemento più grande perché nell'heap ci sono esattamente k-1 elementi più grandi di essa.
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)Trovare k coppie con la somma più piccola
Find K pairs with smallest sums (LeetCode #373) usa un min-heap per generare le coppie in ordine. Inizi con tutte le coppie (nums1[0], nums2[j]) per ogni j. Rimuova il minimo e, per la coppia rimossa (nums1[i], nums2[j]), inserisca (nums1[i+1], nums2[j]), ovvero il candidato successivo della stessa colonna di nums2. Questo è uno schema comune per generare coppie o prodotti ordinati con un 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]]Scheduler di attività con un max-heap
Task Scheduler (LeetCode #621) richiede di calcolare il tempo minimo per pianificare n attività, con un intervallo di raffreddamento di n unità tra due esecuzioni della stessa attività. Utilizzi un max-heap delle frequenze delle attività: a ogni istante scelga l'attività disponibile più frequente, ne decrementi il conteggio e la metta in cooldown. Elabori k=n+1 attività per ciclo, oppure completi il ciclo con intervalli inattivi. Questo approccio greedy con un max-heap produce la risposta ottimale.
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 nell'algoritmo di Dijkstra
La coda con priorità nell'algoritmo di Dijkstra viene implementata con un min-heap. Memorizzi tuple (distance, node) ed elabori sempre per primo il nodo non visitato più vicino. Quando rimuove un nodo con una distanza maggiore del cammino minimo attualmente noto (una voce obsoleta dovuta alla cancellazione lazy), lo ignori. In questo modo non è necessaria un'operazione decrease-key e l'implementazione rimane semplice, mantenendo al contempo la complessità O((V + E) log V).
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}Riorganizzare una stringa con un max-heap
Reorganize String (LeetCode #767) richiede di riordinare una stringa in modo che non vi siano due caratteri adiacenti uguali. Utilizzi un max-heap di (-frequency, char). A ogni passaggio rimuova il carattere più frequente. Se il carattere precedente coincide con quello più frequente, rimuova invece il secondo più frequente. Questo approccio greedy garantisce che il carattere più vincolato venga collocato il prima possibile.
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)Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato l'API del modulo heapq di Python, inclusi heapify, heappush, heappop, nlargest, nsmallest e merge; la simulazione di un max-heap tramite la negazione dei valori; e gli schemi comuni degli heap nei colloqui tecnici, tra cui lo streaming top-k, il k-esimo elemento più grande in uno stream, lo scheduler di attività e Dijkstra. Nella prossima lezione affronteremo la mediana di uno stream di dati e l'unione k-way.
Domande Frequenti
La lezione «heapq di Python e trucchi per il max-heap» è gratuita?
Sì — il testo completo di «heapq di Python e trucchi per il max-heap» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «heapq di Python e trucchi per il max-heap»?
Usi heapq.heappush/heappop, neghi i valori per simulare un max-heap e applichi heapq.nlargest/nsmallest a rapide query top-k Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «heapq di Python e trucchi per il max-heap»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Proprietà degli heap e rappresentazione tramite array
- Heapify, push e pop da zero
- heapq di Python e trucchi per il max-heap
- Mediana da un flusso di dati e merge k-way