I'm using heapq module to heap-sort a list of tuples.
However, for tie on the first tuple's key, heapq does not auto fallback to the next key:
import heapq
x = [(3, 0, 0), (6, 0, 1), (2, 1, 0), (3, 1, 1)]
heapq.heapify(x)
print(x)
Will print:
[(2, 1, 0), (3, 1, 1), (3, 0, 0), (6, 0, 1)]
I expect (3, 0, 0) should come before (3, 1, 1). Do I need to specify a customized comparison method? or how do I make this work?
As the documentation states,
its smallest element is always the root, heap[0]
but that doesn't mean that the other elements are ordered. After calling heapify(), you get
[(2, 1, 0), (3, 1, 1), (3, 0, 0), (6, 0, 1)]
When you remove the first (smallest) item, the heap will reorder itself:
heapq.heappop(x) # returns (2, 1, 0)
print(x)
gives
[(3, 0, 0), (3, 1, 1), (6, 0, 1)]
To get the full ordered list, implement a heapsort() function as described in the examples.