python - 在 Python 中按值对元素进行排序的数据结构

Question

我需要一个队列结构，在插入时按值对元素（id、值）进行排序。另外，我需要能够删除具有最高值的元素。我不需要这个结构是线程安全的。在 Java 中，我猜这对应于 PriorirtyQueue。

我应该在 Python 中使用什么结构？你能提供一个玩具的例子吗？

Answer 1

Python 有类似的东西（它实际上是一个线程安全的包装器heapq）：

from Queue import PriorityQueue

q = PriorityQueue()
q.put((-1, 'foo'))
q.put((-3, 'bar'))
q.put((-2, 'baz'))

您可以通过以下方式获得最小的数字，而不是最大的数字q.get()：

>>> q.get()
(-3, 'bar')

如果您不喜欢底片，可以覆盖该_get方法：

class PositivePriorityQueue(PriorityQueue):
    def _get(self, heappop=max):
        return heappop(self.queue)

Answer 2

您可以使用该heapq模块。

来自文档：

该模块提供了堆队列算法的实现，也称为优先队列算法。

Answer 3

我认为您要查找的内容可以在 heapq 库中找到。来自http://docs.python.org/2/library/heapq.html：

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:

>>> import heapq
>>>
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

这是期望的行为吗？

Answer 4

heapq使用优先级队列，但它是最小堆，因此您需要将值设为负数。此外，您需要将 id 放在第二位，因为排序是从左到右完成的。

>>> import heapq
>>> queue = []
>>> heapq.heappush(queue, (-1, 'a'))
>>> heapq.heappush(queue, (-2, 'a'))
>>> heapq.heappop(queue)
(-2, 'a')