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.
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
import heapq
heapq.heapify(preturi)
for _ in range(k):
print(heapq.heappop(preturi))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
while True:
d, nod = heapq.heappop(heap)
if nod == tinta:
return dwhile heap:
d, nod = heapq.heappop(heap)
if nod == tinta:
return d
return -1Dacă ținta nu se poate atinge, heap-ul se golește. while heap oprește bucla, iar return -1 spune că nu există drum.
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 [].
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))[3, 5] [2, 9] []
Indiciu
Nu scoate din heap de mai multe ori decât elemente are.
Reparația
import heapq
def cele_mai_ieftine(preturi, k):
heap = list(preturi)
heapq.heapify(heap)
rezultat = []
while heap and len(rezultat) < 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))De ce merge
Bucla for _ in range(k) scotea de exact k ori, chiar dacă heap-ul avea doar două prețuri, iar a treia scoatere găsea lista goală. while heap and len(rezultat) < k se oprește la prima dintre cele două condiții: s-au strâns k prețuri sau nu mai e nimic de scos. heapify e O(n), iar fiecare scoatere O(log n). Copia list(preturi) evită modificarea listei primite.
Alte forme ale mesajului
IndexError: list index out of rangeIndexError: 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
TypeError: '<' not supported between instances of 'Nod' and 'Nod' Ai pus în heapq tupluri (prioritate, obiect), iar două elemente au aceeași prioritate, așa că heapq a încercat să compare obiectele, care nu știu să se compare. Adaugă un contor unic între ele: (prioritate, contor, obiect). IndexError: pop from empty list Ai apelat stiva.pop() pe o stivă goală. La verificarea parantezelor înseamnă de obicei o paranteză închisă fără pereche. Verifică înainte cu if not stiva: (și tratează cazul) sau pune condiția în while stiva and ... IndexError: pop from an empty deque Ai apelat coada.popleft() (sau pop()) pe un deque gol: bucla a continuat după ce coada s-a golit, sau ai scos de două ori pentru un singur element pus. Folosește while coada: și scoate un singur element pe iterație. Î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.
