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

IndexError: index out of range la heapq.heappop

Pe scurt

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.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

heapq lucrează pe o listă obișnuită. heapq.heappop(heap) scoate cel mai mic element; dacă lista e goală, aruncă IndexError: index out of range. Mesajul e mai scurt decât cel de la liste (list index out of range) sau de la pop() (pop from empty list), de aceea uneori e greu de recunoscut.

Cazurile tipice: scoți de k ori dintr-un heap care are mai puțin de k elemente; o buclă de tip Dijkstra sau planificare are altă condiție decât while heap; citești vârful cu heap[0] pe un heap gol (mesajul devine list index out of range).

Decide ce trebuie să facă funcția când nu mai sunt elemente: să se oprească, să returneze None sau să returneze câte elemente a găsit. Cererea „primele k” cu mai puțin de k elemente e un caz limită pe care testele îl verifică des.

De ce apare: cauzele frecvente

1Mai multe scoateri decât elemente

Greșit
PYTHON
import heapq
heapq.heapify(preturi)
for _ in range(k):
    print(heapq.heappop(preturi))
Corect
PYTHON
import heapq
heapq.heapify(preturi)
for _ in range(min(k, len(preturi))):
    print(heapq.heappop(preturi))

Dacă k e mai mare decât numărul de prețuri, ultimele scoateri găsesc heap-ul gol. Limitează numărul de scoateri.

2Bucla nu verifică heap-ul

Greșit
PYTHON
while True:
    d, nod = heapq.heappop(heap)
    if nod == tinta:
        return d
Corect
PYTHON
while heap:
    d, nod = heapq.heappop(heap)
    if nod == tinta:
        return d
return -1

Dacă ținta nu se poate atinge, heap-ul se golește. while heap oprește bucla, iar return -1 spune că nu există drum.

Repară tu

Repară eroarea, direct în pagină

Funcția cele_mai_ieftine(preturi, k) returnează cele mai mici k prețuri, în ordine crescătoare, cu un heap. Când k e mai mare decât numărul de prețuri, dă IndexError: index out of range. Repar-o ca să returneze câte prețuri există și să afișeze [3, 5], [2, 9] și [].

Codul care dă eroarea
PYTHON
import heapq

def cele_mai_ieftine(preturi, k):
    heap = list(preturi)
    heapq.heapify(heap)
    rezultat = []
    for _ in range(k):
        rezultat.append(heapq.heappop(heap))
    return rezultat

print(cele_mai_ieftine([12, 5, 8, 3, 20], 2))
print(cele_mai_ieftine([9, 2], 5))
print(cele_mai_ieftine([], 3))
După reparație, programul afișează
[3, 5]
[2, 9]
[]
Indiciu

Nu scoate din heap de mai multe ori decât elemente are.

Alte forme ale mesajului

  • IndexError: list index out of range
  • IndexError: pop from empty list

Cum o eviți pe viitor

Scrie buclele cu heap mereu ca while heap: și decide după buclă ce returnezi când n-ai găsit nimic. La „primele k” folosește heapq.nsmallest(k, lista) / heapq.nlargest(k, lista), care întorc atâtea elemente câte există, sau limitează numărul de scoateri cu min(k, len(heap)). Testează cu k mai mare decât numărul de elemente și cu un graf în care ținta nu se poate atinge.

Întrebări frecvente

De ce mesajul nu spune list index out of range?

heappop e scris în C și aruncă direct IndexError('index out of range'), fără să menționeze lista. E tot un heap gol.

Cum obțin cel mai mare element cu heapq?

heapq e un min-heap. Pentru maxim pune valorile cu semn schimbat (-x) și schimbă semnul înapoi la scoatere, sau folosește heapq.nlargest.

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.