在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)

有什么建议吗？

- Nullpoet

---

可能是重复的问题：如何使heapq根据特定属性评估堆？ - Cristian Ciupitu

Answer 1

解决方案：使用新比较器包装数据

由于内置函数不直接支持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

- Raymond Hettinger

---

我认为在这种情况下，他希望优先级是从对象中推导出来而不是手动指定的。 - agf

当任务是 np.array 时，这也会引起麻烦，因为它们在比较时不会产生布尔值。 - Eric

@Eric 出于好奇，您认为 heapq 与 np.array 有什么关系？ - Raymond Hettinger

我的观点更多是提供另一个示例，说明当任务本身不可比较时会出现问题。我不希望heapq可以处理ndarrays列表。 - Eric

那么元组的第一个元素总是被用作键吗？ - information_interchange

使用id(task)作为元组的第二个元素，使用任务作为第三个元素应该可以防止实际任务被比较。 - jpgeek

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稳定，你需要进行更复杂的比较。

- agf

---

PEP 8 建议定义所有六个比较运算符，而不是依赖于使用者函数的实现细节。 - Raymond Hettinger

@RaymondHettinger 我知道这是一般的建议，但在这种情况下已经知道需要什么--使用情境不是任意比较，而是为了特定目的。如果你只在一个上下文中操作，那么“最好实现所有六个操作，以免在其他上下文中产生混淆”就不适用了。 - agf

添加“@functools.total_ordering”很容易，就可以轻松地支持所有六个操作。此外，PEP 8规范也适用于使用堆的内容。使用“__lt__()”是一种特定于实现的细节，可能会更改。不久前，它使用的是“__le__()”。 - Raymond Hettinger

当我开始像@RaymondHettinger的答案中那样使用元组时，与使用为该类定义的排序相比，我发现速度显着提高了。 - Joel

Answer 3

通过这些Heap和HeapBy类，我试图简化heapq的使用。使用HeapBy可以传递一个键排序函数。

请注意，Raymond表示如果优先级重复且值不可排序，则他的解决方案无法使用。这就是为什么我添加了一个使用NonComparable类的HeapBy示例。

我从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

- Ferran Maylinch

Answer 4

好吧，这是可怕的，绝对不应该这样做...但看起来heapq模块定义了一个cmp_lt函数，如果你真的想要一个自定义比较函数，你可以使用monkey patch。

- David Wolever

---

为什么会糟糕呢？这个方法对我来说很有效！我甚至可以使用这种方法实现最大堆。 - Nullpoet

如果不小心操作的话，使用heapq模块会让其他代码遭受可怕的破坏和损害，而试图对heapq模块进行猴子补丁操作的代码则会变得更加糟糕。最好的方法是遵循Raymond Hettinger的建议，他是Python中实现此类算法模块的作者之一。 - David Wolever

好的，这很糟糕，但为什么 import heapq 然后 heapq.cmp_lt = lambda x, y: x.value < y.value 不起作用呢？（在我的情况下，我将比较具有值的节点）。 - Csaba Toth

Answer 5

我不知道这是否更好，但它类似于Raymond Hettinger的解决方案，但优先级是从对象中确定的。

让这个对象成为您要按x属性排序的对象。

class Item:                                 
    def __init__(self, x):
        self.x = x

然后编写一个应用配对的函数。

def create_pairs(items):
     return map(lambda item: (item.x, item), items)

然后将该函数应用于作为输入传递给heapq.merge的列表。

list(heapq.merge(create_pairs([Item(1), Item(3)]), 
                 create_pairs([Item(2), Item(5)])))

以下是输出结果：

这给了我以下输出

[(1, <__main__.Item instance at 0x2660cb0>),
 (2, <__main__.Item instance at 0x26c2830>),
 (3, <__main__.Item instance at 0x26c27e8>),
 (5, <__main__.Item instance at 0x26c2878>)]

- Cameron White