Sorting tuples with heapq-CodePudding

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?

CodePudding user response：

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.

CodePudding user response：

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.