我使用的是python2.6。它在更高版本的python中可用吗?
还有没有其他方法可以为非平凡类的对象列表维护优先级队列?我需要的是这样的东西
>>> l = [ ['a', 3], ['b', 1] ]
>>> def foo(x, y):
... return x[1]-y[1]
>>> heap = heapify(l, cmp=foo)
有什么建议吗?
发布于 2011-10-19 00:56:49
传统的解决方案是在堆上存储(优先级,任务)元组:
pq = [ ]
heappush(pq, (10, task1))
heappush(pq, (5, task2))
heappush(pq, (15, task3))
priority, task = heappop(pq)
只要没有两个任务具有相同的优先级,这就可以很好地工作;否则,将比较任务本身(这在Python3中可能根本不起作用)。
常规文档给出了如何使用heapq实现优先级队列的指导:
http://docs.python.org/library/heapq.html#priority-queue-implementation-notes
发布于 2011-10-18 14:25:59
只需为列表中的对象编写适当的__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]
虽然定义所有比较或使用functools.total_ordering
是一个好主意,但Python只需要__lt__
进行排序。
您可以看到,它是通过使用两个具有相同第一值和不同第二值的项来工作的。无论第二个值是什么,当您执行heapify
时,这两个对象将交换位置,因为lst[0] < lst[1]
将始终为False
。如果你需要heapify
是稳定的,你需要一个更复杂的比较。
发布于 2011-10-18 14:29:03
这太可怕了,你绝对不应该这么做,…但它看起来像heapq
模块defines a cmp_lt
function,如果你真的想要一个自定义的比较函数,你可以随意修补它。
https://stackoverflow.com/questions/7803121
复制相似问题