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

heappop nu scoate minimul: ai adăugat în heap cu append în loc de heappush

Pe scurt

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

Greșit
PYTHON
heapq.heapify(sarcini)
sarcini.append((0, 'bug urgent'))
Corect
PYTHON
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ă

Greșit
PYTHON
heap[2] = (0, 'deploy')
print(heapq.heappop(heap))
Corect
PYTHON
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

Greșit
PYTHON
heap = [5, 1, 4]
print(heapq.heappop(heap))  # 5
Corect
PYTHON
heap = [5, 1, 4]
heapq.heapify(heap)
print(heapq.heappop(heap))  # 1

heappop pe o listă oarecare scoate primul element, nu minimul. O listă devine heap doar după heapify sau dacă e construită numai cu heappush.

Repară tu

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.

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

Elementele noi intră în heap doar prin funcția potrivită din heapq.

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

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