CODEWITHSUNDEEP
pythonpython-3.x
marco.jantke
marco.jantke

Reputation: 91

Heapq module losing elements on heappop

I was playing around with the heapq module and experienced awkward behaviour, though I only use the built in functions modifying it. I created a sample to show the behaviour. My Python version is 3.5.1+. In the sample I would expect 6 elements in the final output, but somehow it looses 3 of them.

from heapq import *

h = []
heappush(h, 1000000000)
heappush(h, 100000000)
heappush(h, 10000000)
heappush(h, 1000000)
heappush(h, 100000)
heappush(h, 10000)

print(h)
print(len(h))

sorted = [heappop(h) for x in h]
print(sorted)

Output on the console:

$ python3 heapq_sample.py
[10000, 1000000, 100000, 1000000000, 10000000, 100000000]
6
[10000, 100000, 1000000]

Can anyone identify the problem or explain the behaviour?

Upvotes: 0

Views: 197

Answers (1)

marco.jantke
marco.jantke

Reputation: 91

I figured out the problem now on my own and want to give an explanation. The problem is not related with the heapq module, but rather with modifying the list while iterating over it. With the heappop function we remove the first element from the list and return it. I am showing the influence of this on the list and mark the current element in the iteration as bold:

  • Iteration 1:

    [10000, 1000000, 100000, 1000000000, 10000000, 100000000]

  • Iteration 2

    [1000000, 100000, 1000000000, 10000000, 100000000]

  • Iteration 3

    [1000000, 1000000000, 10000000, 100000000]

In Iteration 3 another element is popped and python wants to jump in "Iteration 4" to the 4th element in the list which is not given anymore and thats why it raises the StopIteration.

Upvotes: 2

Related Questions