在Python中,heapq.heapify不会将cmp或key函数作为像sorted这样的参数

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

传统的解决方案是在堆上存储(优先级,任务)元组:

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 2

只需__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]

只有__lt__Python需要进行排序,尽管定义所有比较或使用是个好主意functools.total_ordering.

您可以通过使用具有相同第一个值和不同第二个值的两个项来查看它是否正常工作.当你heapify无论第二个值是什么时,这两个对象都会交换位置,因为它lst[0] < lst[1]总是如此False.如果您需要heapify稳定,则需要进行更复杂的比较.

Answer 3

通过这些Heap和HeapBy类，我尝试简化heapq. 您可以使用HeapBy传递键排序功能。

\n\n

请注意，雷蒙德说，如果优先级重复并且值不可排序，他的解决方案将不起作用。这就是为什么我添加了HeapBy一个NonComparable类的示例。

\n\n

我__lt__从agf 的解决方案中得到了这个想法。

\n\n

用法：

\n\n

# Use HeapBy with a lambda for sorting\nmax_heap = HeapBy(key=lambda x: -x)\nmax_heap.push(3)\nmax_heap.push(1)\nmax_heap.push(2)\nassert max_heap.pop() == 3\nassert max_heap.pop() == 2\nassert max_heap.pop() == 1\n\n# Use Heap as a convenience facade for heapq\nmin_heap = Heap()\nmin_heap.push(3)\nmin_heap.push(1)\nmin_heap.push(2)\nassert min_heap.pop() == 1\nassert min_heap.pop() == 2\nassert min_heap.pop() == 3\n\n#\xc2\xa0HeapBy also works with non-comparable objects.\n# Note that I push a duplicated value\n# to make sure heapq will not try to call __lt__ on it.\n\nclass NonComparable:\n    def __init__(self, val):\n        self.val = val\n\n# Using non comparable values\nmax_heap = HeapBy(key=lambda x: -x.val)\nmax_heap.push(NonComparable(1))\nmax_heap.push(NonComparable(1))\nmax_heap.push(NonComparable(3))\nmax_heap.push(NonComparable(2))\nassert max_heap.pop().val == 3\nassert max_heap.pop().val == 2\nassert max_heap.pop().val == 1\nassert max_heap.pop().val == 1\n

\n\n

课程：

\n\n

import heapq\n\nclass Heap:\n    """\n    Convenience class for simplifying heapq usage\n    """\n\n    def __init__(self, array=None, heapify=True):\n        if array:\n            self.heap = array\n            if heapify:\n                heapq.heapify(self.heap)\n        else:\n            self.heap = []\n\n    def push(self, x):\n        heapq.heappush(self.heap, x)\n\n    def pop(self):\n        return heapq.heappop(self.heap)\n\n\nclass HeapBy(Heap):\n    """\n    Heap where you can specify a key function for sorting\n    """\n\n    # Item only uses the key function to sort elements,\n    # just in case the values are not comparable\n    class Item:\n        def __init__(self, value, key):\n            self.key = key\n            self.value = value\n        def __lt__(self, other):\n            return self.key(self.value) < other.key(other.value)\n\n    def __init__(self, key, array=None, heapify=True):\n        super().__init__(array, heapify)\n        self.key = key\n\n    def push(self, x):\n        super().push(self.Item(x, self.key))\n\n    def pop(self):\n        return super().pop().value\n

\n