如何反转 python 中 PriorityQueue 的顺序？

Question

我在 python 中创建了一个简单的优先级队列，它按项目的价值排序：

import Queue
q = Queue.PriorityQueue()
for it in items:
    q.put((it.value, it))

但是当我打印队列时使用：

while not q.empty()
    print q.get()

它总是先打印最小值。有没有办法在不将代码顶部的最后两行更改为：

的情况下获取队列中的最后一项

for it in items:
    q.put((-1*it.value, it))

因为这看起来有点混乱，如果我想将该信息用于其他用途（我将不得不再次将其乘以 -1）会产生问题

Answer 1

根据spec（假设python 2.7）：

The lowest valued entries are retrieved first

所以这意味着，不，你不能。

Answer 2

根据定义，您只能从队列的前面检索项目。要颠倒顺序，您可以将所有内容压入堆栈，然后从堆栈中弹出项目。由于堆栈从其后面添加和检索项目，这与反转队列具有相同的效果。

Answer 3

在Queue.PriorityQueue

的情况下

The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]).

所以你可以试试queue.LifoQueue。它是LIFO机制。

Answer 4

您可以使转换透明。

你想要的是有一个新的 q.get 和一个新的 q.put 透明地修改队列中和队列外的数据以反转顺序：

# new reversed priority put method
q.oldput = q.put
q.put = lambda p, i: q.oldput((p * -1, i))

# new reversed priority get method
q.oldget = q.get
# create get closure for queue
def newget(q):
    def g():
        item = q.oldget()
        # reverse first element
        return item[0] * -1, item[1]
    # return get method for given queue
    return g
# bind to queue
q.get = newget(q)

# test
items = range(10)
for it in items:
    q.put(*(it, it))

while not q.empty():
    print q.get()

如果这是一个更健壮的代码，我强烈建议使用 class 而不仅仅是重新绑定方法。

Answer 5

你可以只做你自己的 class 继承自 PriorityQueue 并在后台为你做混乱的 -1 乘法：

class ReversePriorityQueue(PriorityQueue):

def put(self, tup):
    newtup = tup[0] * -1, tup[1]
    PriorityQueue.put(self, newtup)

def get(self):
    tup = PriorityQueue.get(self)
    newtup = tup[0] * -1, tup[1]
    return newtup

这似乎适用于元组，至少：

Q = ReversePriorityQueue()

In [94]: Q.put((1,1))

In [95]: Q.get()
Out[95]: (1, 1)

In [96]: Q.put((1,1))

In [97]: Q.put((5,5))

In [98]: Q.put((9,9))

In [99]: Q.get()
Out[99]: (9, 9)

In [100]: Q.get()
Out[100]: (5, 5)

In [101]: Q.get()
Out[101]: (1, 1)

我相信您可以将代码概括为不仅可以从这里处理元组。

Answer 6

您可以使用自定义 Class 而不是元组。然后你就可以在cmp中做任何你想做的事了。

Answer 7

如果您想在放入优先级队列时避免乘以-1。你可以这样做。

制作包装器class

class Wrapper:
    def __init__(self, value):
        self.value = value
    
    def __lt__(self, next):
        return self.value[0] > next.value[0]

请注意，我已经修改了 __lt__ 函数，我故意使用 > 而不是 <。

现在将一个元素放入优先队列

from queue import PriorityQueue
pq = PriorityQueue()
pq.put(Wrapper((priority, 'extra data')))

现在在获取元素时确保使用 value 属性来代替

t = pq.get().value

如何反转 python 中 PriorityQueue 的顺序？

How do I reverse the order of PriorityQueue in python?

python

queue

priority-queue