CODEWITHSUNDEEP
pythonpython-2.7heapheapsort
Leo
Leo

Reputation: 89

Heappop() not invariant

When I use heapq.heappop(queue), the first item on the list is popped, but the remaining list is modified. How can I prevent this? (note tuples containing 'r' and 'o' below)

This is my debug output:

Queue: PQ:[(1, 2, 'z'), (1, 3, 't'), (2, 4, 'r'), (2, 5, 'o'), (2, 6, 'f')]

Queue Before Pop: [(1, 2, 'z'), (1, 3, 't'), (2, 4, 'r'), (2, 5, 'o'), (2, 6, 'f')]

priority, counter, node = heapq.heappop(queue)

item returned: (1, 2, 'z') Queue After Pop: [(1, 3, 't'), (2, 5, 'o'), (2, 4, 'r'), (2, 6, 'f')]

The counter is supposed to make sure earlier additions of a node go closer to queue[0].

My queue after pop doesn't just pop heap[0], it rearranges and puts tuple containing 'o' before tuple containing 'r'. Their priority is the same (2), but their counter is 5 and 4 respectively, therefore, they are rearranged in the wrong order.

Inst heappop() only suppose to return heap[0] and move everything else up in the queue? How can I prevent this rearranging?

Upvotes: 0

Views: 346

Answers (1)

jasonharper
jasonharper

Reputation: 9597

This is the normal, expected behavior of a heap. There is NO implied ordering between arbitrary elements of the heap: the only invariant is that each node is less than either of its children. Once your (1,3,'t') element is popped, (2,4,'r') will be chosen as the new root since it is the lesser of the former root's two children; its ordering relative to (2,5,'o') is not relevant until that point in time. In other words, the root is the ONLY element for which you can say anything about its value based upon its index in the heap.

If you want a list that is in completely sorted order at all times, you want the bisect module, not heapq. The performance will be much worse, of course.

Upvotes: 2

Related Questions