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?
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.