python - 在python中合并堆模块中的元组

Question

我想了解 heap.merge() 的合并行为。合并元组列表时，heapq.merge() 是如何决定顺序的？

我有两个列表，每个列表都有一个三元组，

A = [(a, b, c)]
B = [(x, y, z)]

其中 3 元组的类型为 (int, int, str)。我想合并这两个列表。我正在使用 heapq.merge() 操作，因为它非常高效并且针对大型列表进行了优化。 A 和 B 可能包含数百万个三元组。

是否保证 heap.merge() 将输出给定两个元组的顺序，

a >= x and b >= y and c >= z?

Answer 1

Python 对 lexicographic order 中的元组进行排序:

first the first two items are compared, and if they differ this determines the outcome of the comparison; if they are equal, the next two items are compared, and so on, until either sequence is exhausted.

---

举个例子，

In [33]: import heapq    
In [34]: A = [(1,100,2)]    
In [35]: B = [(2,0,0)]

In [40]: list(heapq.merge(A,B))
Out[40]: [(1, 100, 2), (2, 0, 0)]

In [41]: (1, 100, 2) < (2, 0, 0)
Out[41]: True

因此，这不一定是真的

a >= x and b >= y and c >= z

---

可以使用 heapq在任何可订购对象的集合上，包括自定义类的实例。使用自定义类，您可以安排任何您喜欢的排序规则。例如，

class MyTuple(tuple):
    def __lt__(self, other):
        return all(a < b for a, b in zip(self, other))
    def __eq__(self, other):
        return (len(self) == len(other)
                and all(a == b for a, b in zip(self, other)))
    def __gt__(self, other):
        return not (self < other or self == other)            
    def __le__(self, other):
        return self < other or self == other
    def __ge__(self, other):
        return not self < other

A = [MyTuple((1,100,2))]
B = [MyTuple((2,0,0))]
print(list(heapq.merge(A,B)))
# [(2, 0, 0), (1, 100, 2)]

但是请注意，尽管这改变了我们对 < 的概念对于 MyTuple , heapq.merge 返回的结果不保证满足

a <= x and b <= y and c <= z

为此，我们必须先从 A 中删除所有项目和 B这是相互不可排序的。