Heappop and nsmallest from heapq

Question

I have another heapq question, that I hope I can get some clarity on.

I have a list:

rooms = [[0, 2], [0, 3], [9, 0], [0, 4], [0, 1]]

The smallest element in this list is correctly identified by nsmallest as:

nsmallest(1, rooms)[0]

output:
[0, 1] 

However when I use heappop to remove the smallest element, it removes [0, 2]:

a, b = heappop(rooms)
print([a, b])

output:
[0, 2]

However if I sort rooms first, it will pop the correct element. Why do I need to sort rooms?

Answer 1

A heap (according to heapq) is a list that satisfies the heap property

heap[k] <= heap[2*k + 1], for all k>=0 s.t. 2*k + 1 < len(heap)
heap[k] <= heap[2*k + 2], for all k>=0 s.t. 2*k + 2 < len(heap)

nsmallest takes an arbitrary iterable as an argument, and constructs a heap in order to produce its result.

heappop takes a pre-made heap as an argument and modifies it, preserving the heap property in the process.

In your example, rooms is not a heap, because rooms[1] == [0, 3] is not less than rooms[2*1 + 2] == rooms[4] == [0, 1], so heappop(rooms) is not guaranteed to work.

Answer 2

heapq assumes that the list you are using has the order of a heap. If it does not have the order of a heap, it will show wrong results. So you need to heapify your list first, then try to use heappop. Here is the modified version of your code :

from heapq import *
rooms = [[0, 2], [0, 3], [9, 0], [0, 4], [0, 1]]
heapify(rooms)

the rooms will become like :

[[0, 1], [0, 2], [9, 0], [0, 4], [0, 3]]

Now if you call heappop() you'll see the mentioned result :

heappop(rooms)

result :

[0, 1]