在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

我创建了这两个类 Heap 和 HeapBy，目的是让使用 heapq 变得更简单。你可以用 HeapBy 来传入一个用于排序的函数。

需要注意的是，Raymond 提到他的 解决方案 在优先级重复且值不可排序的情况下是行不通的。因此，我添加了一个使用 HeapBy 和 NonComparable 类的例子。

我从 agf 的解决方案 中借鉴了 __lt__ 的想法。

用法：

# Use HeapBy with a lambda for sorting
max_heap = HeapBy(key=lambda x: -x)
max_heap.push(3)
max_heap.push(1)
max_heap.push(2)
assert max_heap.pop() == 3
assert max_heap.pop() == 2
assert max_heap.pop() == 1

# Use Heap as a convenience facade for heapq
min_heap = Heap()
min_heap.push(3)
min_heap.push(1)
min_heap.push(2)
assert min_heap.pop() == 1
assert min_heap.pop() == 2
assert min_heap.pop() == 3

# HeapBy also works with non-comparable objects.
# Note that I push a duplicated value
# to make sure heapq will not try to call __lt__ on it.

class NonComparable:
    def __init__(self, val):
        self.val = val

# Using non comparable values
max_heap = HeapBy(key=lambda x: -x.val)
max_heap.push(NonComparable(1))
max_heap.push(NonComparable(1))
max_heap.push(NonComparable(3))
max_heap.push(NonComparable(2))
assert max_heap.pop().val == 3
assert max_heap.pop().val == 2
assert max_heap.pop().val == 1
assert max_heap.pop().val == 1

类：

import heapq

class Heap:
    """
    Convenience class for simplifying heapq usage
    """

    def __init__(self, array=None, heapify=True):
        if array:
            self.heap = array
            if heapify:
                heapq.heapify(self.heap)
        else:
            self.heap = []

    def push(self, x):
        heapq.heappush(self.heap, x)

    def pop(self):
        return heapq.heappop(self.heap)


class HeapBy(Heap):
    """
    Heap where you can specify a key function for sorting
    """

    # Item only uses the key function to sort elements,
    # just in case the values are not comparable
    class Item:
        def __init__(self, value, key):
            self.key = key
            self.value = value
        def __lt__(self, other):
            return self.key(self.value) < other.key(other.value)

    def __init__(self, key, array=None, heapify=True):
        super().__init__(array, heapify)
        self.key = key

    def push(self, x):
        super().push(self.Item(x, self.key))

    def pop(self):
        return super().pop().value

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]

其实，Python 排序只需要 __lt__ 方法，但定义所有比较方法或者使用 functools.total_ordering 是个不错的主意。

你可以通过使用两个第一个值相同但第二个值不同的对象来验证它是否有效。当你使用 heapify 时，这两个对象会互换位置，无论第二个值是什么，因为 lst[0] < lst[1] 总是会返回 False。如果你希望 heapify 的结果是稳定的，那么你需要一个更复杂的比较方法。

Answer 3

解决方案：用新的比较方式包装数据

因为内置函数不直接支持 cmp 函数，所以我们需要创建新的 heapify 和 heappop 变体：

from heapq import heapify, heappop
from functools import cmp_to_key

def new_heapify(data, cmp):
    s = list(map(cmp_to_key(cmp), data))
    heapify(s)
    return s

def new_heappop(data):
    return heappop(data).obj

这些用法和你的例子是一样的：

>>> l = [ ['a', 3], ['b', 1] ]
>>> def foo(x, y):
...    return x[1]-y[1]
...
>>> heap = new_heapify(l, cmp=foo)
>>> new_heappop(heap)
['b', 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