如何使heapq根据特定属性评估堆？

Question

我想要存放一堆对象，而不仅仅是数字。这些对象里面会有一个整数属性，堆可以根据这个属性来排序。在Python中，使用堆最简单的方法是用heapq库，但我该怎么告诉它在使用heapq时要根据特定的属性来排序呢？

Answer 1

根据官方文档，解决这个问题的方法是把条目存储为元组（请查看8.4.1和8.4.2部分）。

举个例子，你的对象可以用元组的格式表示为(key, value_1, value_2)。

当你把这些对象（也就是元组）放进堆里时，它会先比较对象的第一个属性（在这个例子中是key）。如果有相同的情况，堆会继续比较下一个属性（也就是value_1），依此类推。

例如：

import heapq

heap = []
heapq.heappush(heap, (0,'one', 1))
heapq.heappush(heap, (1,'two', 11))
heapq.heappush(heap, (1, 'two', 2))
heapq.heappush(heap, (1, 'one', 3))
heapq.heappush(heap, (1,'two', 3))
heapq.heappush(heap, (1,'one', 4))
heapq.heappush(heap, (1,'two', 5))
heapq.heappush(heap, (1,'one', 1))

show_tree(heap)

输出：

                                      (0, 'one', 1)                                       
                (1, 'one', 1)                                (1, 'one', 4)                
    (1, 'one', 3)         (1, 'two', 3)         (1, 'two', 2)         (1, 'two', 5)     
(1, 'two', 11)

---

关于在Python中美化打印堆的内容（更新了链接）：show_tree()

Answer 2

根据文档中的例子，你可以使用元组（tuple），这样它会根据元组的第一个元素进行排序：

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

所以，如果你不想（或者不能？）使用__cmp__方法，你可以在添加数据的时候手动提取排序的关键字。

需要注意的是，如果一对元组的第一个元素相同，那么接下来的元素会被比较。如果你不想这样，你需要确保每个第一个元素都是唯一的。

Answer 3

heapq 的排序方式和 list.sort 是一样的，所以你只需要在你的类定义里定义一个方法 __cmp__()，这个方法会用来比较这个类的一个实例和另一个同类的实例：

def __cmp__(self, other):
    return cmp(self.intAttribute, other.intAttribute)

在 Python 2.x 中有效。

在 3.x 中使用：

def __lt__(self, other):
    return self.intAttribute < other.intAttribute