...
Eroare Algoritmi și structuri de date · Arbori și heap-uri

heap[-1] nu e cel mai mare element dintr-un min-heap

Pe scurt

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

Greșit
PYTHON
maxim = heap[-1]
Corect
PYTHON
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]

Greșit
PYTHON
al_doilea = heap[1]
Corect
PYTHON
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ă

Greșit
PYTHON
print(heap)
Corect
PYTHON
print(sorted(heap))

Ordinea internă a heap-ului nu e ordinea crescătoare.

Repară tu

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.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
1 9
Indiciu

Doar heap[0] are o semnificație garantată; maximul trebuie căutat în toată lista.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.