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

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

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