heapq scoate cel mai mic element, nu cel mai mare (max-heap lipsă)
heapq din Python e un min-heap: heappop returnează mereu cel mai mic element. Pentru cel mai mare, pune valorile negate (heappush(h, -x), apoi -heappop(h)), folosește heapq.nlargest, sau, din Python 3.14, heappush_max / heappop_max.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Modulul heapq lucrează pe o listă obișnuită și o păstrează ca min-heap: heap[0] e cel mai mic element, iar heappop îl scoate. Nu există un parametru reverse. Dacă ai nevoie de „cele mai mari k scoruri”, „cel mai apropiat de buget de sus” sau de simularea unei cozi cu prioritate maximă și folosești heapq direct, primești exact opusul.
Nu apare nicio eroare, doar rezultate inversate. Trucul standard e negarea: pui -x în heap, iar la scoatere negi din nou. Pentru tupluri, negi doar câmpul de prioritate: (-scor, nume).
Pentru „cele mai mari k” mai e o variantă eficientă: un min-heap de mărime k, din care scoți minimul când depășește k. La final rămân exact cele mai mari k valori, în O(n log k).
De ce apare: cauzele frecvente
1Cele mai mari k cu min-heap direct
import heapq
h = []
for x in scoruri:
heapq.heappush(h, x)
top = [heapq.heappop(h) for _ in range(3)]import heapq
h = []
for x in scoruri:
heapq.heappush(h, -x)
top = [-heapq.heappop(h) for _ in range(3)]Cu valorile negate, cel mai mic din heap corespunde celui mai mare scor.
2Prioritate maximă într-un tuplu
heapq.heappush(h, (prioritate, sarcina))heapq.heappush(h, (-prioritate, sarcina))Tuplurile se compară după primul câmp, deci negarea lui inversează ordinea.
3Varianta scurtă pentru top k
top = sorted(scoruri)[:3]import heapq
top = heapq.nlargest(3, scoruri)sorted(...)[:3] dă cele mai mici trei. nlargest dă cele mai mari, în O(n log k).
Repară eroarea, direct în pagină
Funcția top_scoruri(scoruri, k) folosește heapq ca să returneze cele mai mari k scoruri, descrescător. Testul cu assert pică: rezultatul conține cele mai mici scoruri. Repar-o ca testul să treacă și să afișeze [98, 91, 87].
import heapq
def top_scoruri(scoruri, k):
h = []
for s in scoruri:
heapq.heappush(h, s)
return [heapq.heappop(h) for _ in range(k)]
rez = top_scoruri([72, 91, 55, 98, 87, 60], 3)
assert rez == [98, 91, 87], f'top gresit: {rez}'
print(rez)[98, 91, 87]
Indiciu
Pune în heap scorurile negate și neagă-le din nou când le scoți.
Reparația
import heapq
def top_scoruri(scoruri, k):
h = []
for s in scoruri:
heapq.heappush(h, -s)
return [-heapq.heappop(h) for _ in range(k)]
rez = top_scoruri([72, 91, 55, 98, 87, 60], 3)
assert rez == [98, 91, 87], f'top gresit: {rez}'
print(rez)De ce merge
heapq păstrează mereu cel mai mic element în vârf, deci codul inițial scotea 55, 60 și 72. Punând -s în heap, cel mai mic element din heap e -98, adică cel mai mare scor. La scoatere, -heapq.heappop(h) refacem valoarea reală. Ordinea rezultată e descrescătoare, pentru că scoatem negativele de la cel mai mic la cel mai mare.
Cum o eviți pe viitor
Când scrii import heapq, scrie lângă el un comentariu: „min-heap”. Pentru maxime, alege din start una din variante: negare (merge în orice versiune), nlargest/nsmallest pentru top k, sau funcțiile _max din Python 3.14. Verifică rezultatul pe un exemplu mic, unde știi răspunsul pe de rost.
Întrebări frecvente
Negarea merge și pentru texte?
Nu, -'abc' dă eroare. Pentru texte, pune un tuplu cu o cheie numerică negată sau folosește funcțiile heappush_max și heappop_max din Python 3.14.
De ce heap[0] e minimul, dar restul listei nu e sortat?
Un heap garantează doar că fiecare părinte e mai mic decât copiii lui. E suficient ca minimul să fie mereu la poziția 0, fără costul unei sortări complete.
Erori înrudite
IndexError: index out of range la heapq.heappop heapq.heappop(heap) pe un heap gol aruncă IndexError: index out of range (fără „list”). Verifică while heap: sau if heap: înainte să scoți, iar la „cele mai mari k” nu scoate de mai multe ori decât elemente ai. TypeError: '<' not supported between instances of 'Nod' and 'Nod' Ai pus în heapq tupluri (prioritate, obiect), iar două elemente au aceeași prioritate, așa că heapq a încercat să compare obiectele, care nu știu să se compare. Adaugă un contor unic între ele: (prioritate, contor, obiect). Dijkstra dă distanțe greșite: nodul e marcat vizitat când e pus în heap La Dijkstra, prima distanță găsită spre un nod nu e neapărat cea mai mică. Dacă marchezi nodul ca vizitat când îl pui în heap, nu mai poți îmbunătăți distanța lui. Actualizează distanța ori de câte ori găsești una mai mică și ignoră la scoatere intrările vechi (if d > dist[u]: continue). Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
