5

I'm trying to use the Python module heapq in my program but I ran into a strange problem using heapq.heappop(). The function does not appear to return the smallest element in the heap. Take a look at the following code:

Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import heapq
>>> list = [[1326, 'a'], [654, 'b']]
>>> print heapq.heappop(list)
[1326, 'a']
>>> print heapq.heappop(list)
[654, 'b']

Should heappop() not return [654, 'b'] first and then [1326, 'a']?

Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
jpaulus
  • 53
  • 1
  • 4

1 Answers1

2

You should "heapify" the list first (an in-place operation):

In [1]: import heapq

In [2]: l = [[1326, 'a'], [654, 'b']]

In [3]: heapq.heapify(l)

In [4]: heapq.heappop(l)
Out[4]: [654, 'b']

In [5]: heapq.heappop(l)
Out[5]: [1326, 'a']

And, avoid naming your list as list - you are shadowing the built-in list keyword.

alecxe
  • 462,703
  • 120
  • 1,088
  • 1,195
  • Thanks, that was indeed the problem for the above example. For my code I found that each time I edited the heap I needed to use the sort() function again (silly me). – jpaulus Sep 25 '16 at 15:45