python - 在堆中使用元组进行多维排序？

Question

假设我有一个列表，例如:

[(3,4), (4,3), (1,5), (5,1), (2,6), (6,2)]

我想返回具有最低 x 值的元组以及具有最低 y 值的元组。

是否可以使用索引 0 构建一个(最小)堆，并使用索引 1 构建另一个堆？这将产生两个堆:

for x: [(1,5), (2,6), (3,4), (4,3), (5,1), (6,2)]
#and
for y: [(5,1), (6,2), (4,3), (3,4), (1,5), (2,6)].

我们可以对元组使用堆排序吗？

Answer 1

答案是肯定的，你可以使用heapsort在元组上:

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked...

不过也是mentioned in the docs那:

[nsmallest and nlargest] perform best for smaller values of n. For larger values, it is more efficient to use the sorted() function. Also, when n==1, it is more efficient to use the built-in min() and max() functions.

也就是说，如果你想要最小的y，使用min :

tuple_list = [(3,4), (4,3), (1,5), (5,1), (2,6), (6,2)]

min(tuple_list, key=lambda x: x[1])
# (5,1)

如果您想对整个列表进行排序，请使用 sorted :

sorted(tuple_list, key=lambda x: x[1])
# [(5,1), (6,2), (4,3), (3,4), (1,5), (2,6)]

而如果您想使用三个最小值，请使用 heapq.nsmallest :

heapq.nsmallest(3, tuple_list, key=lambda x: x[1])
# [(5,1), (6,2), (4,3)]