Sorting tuples with heapq

Question

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?

Answer 1

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.

Answer 2

To sort the tuples list using the heapq module, you could implement the heapsort() function as shown in the Basic Examples section of the documentation:

from heapq import heappop, heappush

def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

x = [(3, 0, 0), (6, 0, 1), (2, 1, 0), (3, 1, 1)]

res = heapsort(x)
print(res)  # -> [(2, 1, 0), (3, 0, 0), (3, 1, 1), (6, 0, 1)]

As you can see, (3, 0, 0) will come before (3, 1, 1) as expected.