heappop nu scoate minimul: ai adăugat în heap cu append în loc de heappush
Un heap din heapq e o listă obișnuită care respectă o anumită ordine internă, iar append sau o atribuire directă strică ordinea. Adaugă doar cu heapq.heappush(heap, x), iar dacă ai modificat elemente direct, refă ordinea cu heapq.heapify(heap).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
heapq nu are o clasă specială: heap-ul e o listă Python în care fiecare element e mai mic sau egal cu „copiii” lui (heap[i] <= heap[2*i + 1] și heap[i] <= heap[2*i + 2]). Funcțiile heappush și heappop păstrează această proprietate, așa că heap[0] e mereu minimul.
Dacă adaugi cu heap.append(x) sau schimbi o valoare cu heap[i] = x, lista nu mai respectă regula, dar Python nu are de unde să știe. heappop presupune că ordinea e corectă, scoate heap[0] și reorganizează pe baza ei, așa că poate returna un element care nu e minimul. Nu primești nicio eroare, doar priorități greșite: o sarcină urgentă așteaptă, iar Dijkstra calculează distanțe greșite.
Regula: după heapify, lista se modifică doar prin funcțiile din heapq.
De ce apare: cauzele frecvente
1append pe o listă care e deja heap
heapq.heapify(sarcini)
sarcini.append((0, 'bug urgent'))heapq.heapify(sarcini)
heapq.heappush(sarcini, (0, 'bug urgent'))heappush pune elementul la final și îl urcă până la poziția corectă, deci minimul ajunge în heap[0].
2Prioritatea schimbată direct în listă
heap[2] = (0, 'deploy')
print(heapq.heappop(heap))heap[2] = (0, 'deploy')
heapq.heapify(heap)
print(heapq.heappop(heap))heapify reface ordinea în O(n). La Dijkstra se preferă alt tipar: adaugi o intrare nouă cu heappush și le sari pe cele vechi la scoatere.
3Lista nu a fost transformată în heap
heap = [5, 1, 4]
print(heapq.heappop(heap)) # 5heap = [5, 1, 4]
heapq.heapify(heap)
print(heapq.heappop(heap)) # 1heappop pe o listă oarecare scoate primul element, nu minimul. O listă devine heap doar după heapify sau dacă e construită numai cu heappush.
Repară eroarea, direct în pagină
Programul ține sarcinile într-un heap după prioritate (numărul mai mic e mai urgent). Testul cu assert pică: după adăugarea unui bug urgent, heappop scoate tot emailul. Repară adăugarea ca să afișeze bug urgent, apoi email.
import heapq
sarcini = [(3, 'raport'), (1, 'email'), (2, 'deploy')]
heapq.heapify(sarcini)
sarcini.append((0, 'bug urgent'))
prima = heapq.heappop(sarcini)[1]
adoua = heapq.heappop(sarcini)[1]
assert (prima, adoua) == ('bug urgent', 'email'), f'prioritate gresita: {prima}, {adoua}'
print(prima)
print(adoua)bug urgent email
Indiciu
Elementele noi intră în heap doar prin funcția potrivită din heapq.
Reparația
import heapq
sarcini = [(3, 'raport'), (1, 'email'), (2, 'deploy')]
heapq.heapify(sarcini)
heapq.heappush(sarcini, (0, 'bug urgent'))
prima = heapq.heappop(sarcini)[1]
adoua = heapq.heappop(sarcini)[1]
assert (prima, adoua) == ('bug urgent', 'email'), f'prioritate gresita: {prima}, {adoua}'
print(prima)
print(adoua)De ce merge
După heapify, lista era [(1, 'email'), (3, 'raport'), (2, 'deploy')]. append a pus bug-ul la final, fără să-l compare cu nimic, deci heap[0] a rămas emailul, iar heappop l-a scos primul. heappush adaugă elementul la final și apoi îl urcă spre rădăcină cât timp e mai mic decât părintele, așa că (0, 'bug urgent') ajunge în heap[0] și iese primul.
Cum o eviți pe viitor
Tratează lista heap-ului ca pe o structură închisă: o creezi cu [] sau heapify, adaugi cu heappush, scoți cu heappop sau heapreplace, citești minimul cu heap[0]. Nu folosi append, insert, sort, remove sau atribuiri directe pe ea. Dacă ai nevoie de actualizări de prioritate, adaugă o intrare nouă și ignoră intrările vechi când le scoți.
Întrebări frecvente
Pot sorta lista în loc de heapify?
Da, o listă sortată crescător e și un heap valid. Dar sortarea costă O(n log n), iar heapify O(n), deci heapify e alegerea obișnuită.
Cum șterg un element oarecare din heap?
Fie îl marchezi ca șters și îl sari când apare la heappop, fie îl scoți cu remove și apoi apelezi heapify, ceea ce costă O(n).
Erori înrudite
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. heap[-1] nu e cel mai mare element dintr-un min-heap Un heap garantează doar că heap[0] e minimul; restul listei nu e sortat, deci heap[-1] e o valoare oarecare. Pentru maxim folosește max(heap), un al doilea heap cu valori negate sau heapq.nlargest(1, heap). 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.
