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).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Lista din heapq respectă o singură regulă: fiecare părinte e mai mic sau egal cu copiii lui (heap[i] <= heap[2*i + 1] și heap[i] <= heap[2*i + 2]). De aici rezultă doar că heap[0] e minimul. Ultimul element din listă e ultima frunză, nu maximul.
De exemplu, după ce inserezi 5, 1, 8, 3, 9, 2, lista arată [1, 3, 2, 5, 9, 8]: minimul e pe prima poziție, dar pe ultima e 8, nu 9.
Nu primești nicio eroare. Rezultatul e uneori corect (pe date mici sau deja sortate), de aceea greșeala scapă la primele teste. Același lucru e valabil pentru heap[1] (nu e neapărat al doilea cel mai mic) și pentru parcurgerea listei în ordine.
De ce apare: cauzele frecvente
1Maximul citit de pe ultima poziție
maxim = heap[-1]maxim = max(heap)max verifică toate elementele, O(n). Dacă ai nevoie des de maxim, ține un max-heap separat.
2Al doilea minim citit din heap[1]
al_doilea = heap[1]al_doilea = heapq.nsmallest(2, heap)[1]Al doilea minim poate fi heap[1] sau heap[2]; nsmallest îl găsește corect.
3Lista din heap afișată ca sortată
print(heap)print(sorted(heap))Ordinea internă a heap-ului nu e ordinea crescătoare.
Repară eroarea, direct în pagină
Programul ține prețurile într-un heap și afișează cel mai mic și cel mai mare preț. Testul cu assert pică: „cel mai mare” e citit de pe ultima poziție a listei. Repară-l ca să afișeze 1 9.
import heapq
heap = []
for pret in [5, 1, 8, 3, 9, 2]:
heapq.heappush(heap, pret)
minim, maxim = heap[0], heap[-1]
assert maxim == 9, f'maxim gresit: {maxim}'
print(minim, maxim)1 9
Indiciu
Doar heap[0] are o semnificație garantată; maximul trebuie căutat în toată lista.
Reparația
import heapq
heap = []
for pret in [5, 1, 8, 3, 9, 2]:
heapq.heappush(heap, pret)
minim, maxim = heap[0], max(heap)
assert maxim == 9, f'maxim gresit: {maxim}'
print(minim, maxim)De ce merge
După inserări, lista internă e [1, 3, 2, 5, 9, 8]: regula de heap pune minimul pe prima poziție, dar ultima poziție e doar ultima frunză, cu valoarea 8. max(heap) verifică toate elementele și găsește 9. Minimul rămâne heap[0], care e garantat corect.
Cum o eviți pe viitor
Accesează un heap doar prin heap[0], heappop și heappush. Orice altă poziție din listă e un detaliu intern. Când ai nevoie atât de minim cât și de maxim, folosește două heap-uri (unul cu valori negate) sau o listă sortată cu bisect. Testează cu valori inserate în ordine amestecată.
Întrebări frecvente
Cum fac un max-heap cu heapq?
Inserezi valorile negate (heappush(heap, -x)) și negi la scoatere (-heappop(heap)). Din Python 3.14 există și funcții dedicate, ca heapq.heappush_max.
max(heap) nu strică avantajul heap-ului?
Costă O(n). E în regulă o dată, dar dacă ai nevoie de maxim la fiecare pas, ține un al doilea heap.
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. TypeError: heappush expected 2 arguments, got 1 heapq.heappush primește două argumente: lista heap și elementul. Ai dat doar elementul (de obicei un tuplu). Scrie heapq.heappush(heap, (distanta, nume)). Dacă primești got 3, ai uitat parantezele tuplului. 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. Î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.
