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

heapq scoate cel mai mic element, nu cel mai mare (max-heap lipsă)

Pe scurt

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

Greșit
PYTHON
import heapq
h = []
for x in scoruri:
    heapq.heappush(h, x)
top = [heapq.heappop(h) for _ in range(3)]
Corect
PYTHON
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

Greșit
PYTHON
heapq.heappush(h, (prioritate, sarcina))
Corect
PYTHON
heapq.heappush(h, (-prioritate, sarcina))

Tuplurile se compară după primul câmp, deci negarea lui inversează ordinea.

3Varianta scurtă pentru top k

Greșit
PYTHON
top = sorted(scoruri)[:3]
Corect
PYTHON
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ă tu

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

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[98, 91, 87]
Indiciu

Pune în heap scorurile negate și neagă-le din nou când le scoți.

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

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