在Python中，heapq.heapify不像sorted那样使用cmp或key函数作为参数

Question

我在用Python2.6。它在更高版本的python中可用吗？
还有其他方法可以维护非平凡类对象列表的优先级队列吗？ 我需要的是这样的东西

>>> l = [ ['a', 3], ['b', 1] ]
>>> def foo(x, y):
...   return x[1]-y[1]
>>> heap = heapify(l, cmp=foo)

有什么建议吗？

Answer 1

只需为列表中的对象编写一个适当的__lt__方法，以便它们正确排序：

class FirstList(list):
    def __lt__(self, other):
        return self[0] < other[0]

lst = [ ['a', 3], ['b', 1] ]

lst = [FirstList(item) for item in lst]

Python只需要__lt__来进行排序，不过最好定义所有比较或使用^{}。

您可以看到它是通过使用具有相同第一值和不同第二值的两个项来工作的。当您heapify时，无论第二个值是什么，这两个对象都将交换位置，因为lst[0] < lst[1]将始终是False。如果你需要稳定的heapify，你需要一个更复杂的比较。

Answer 2

传统的解决方案是在堆上存储（优先级，任务）元组：

pq = [ ]
heappush(pq, (10, task1))
heappush(pq, (5, task2))
heappush(pq, (15, task3))
priority, task = heappop(pq)

只要没有两个任务具有相同的优先级，这就可以正常工作；否则，将比较任务本身（这在Python 3中可能根本不起作用）。

常规文档指导如何使用heapq实现优先级队列：

http://docs.python.org/library/heapq.html#priority-queue-implementation-notes

Answer 3

好吧，这太糟糕了，你绝对不应该这么做……但它看起来像heapq模块defines a ^{} function，如果你真的想要一个自定义的比较函数，你可以对它进行修改。