2

我正在尝试学习 Python 的东西，并且想知道是否有人可以帮助我提供一些使用优先级队列的示例。我知道它们在 java 中是如何工作的，但似乎看不到它们在 Python 中如何工作的清晰示例。就像我看到的队列的大小是 .qsize() 从这里：http ://docs.python.org/2/library/queue.html但它没有显示获取最小值、最大值、组织的示例，弹出，添加到队列中，对它们进行排序，遍历它们。如果有人可以给我一个例子或指出我在哪里学习这个的正确方向，我会非常感激。

4

3 回答 3

6

Queue不是您要查找的优先级队列。相反，您正在寻找heapq适用于 Pythonlist的 . 您可以使用空列表 ( []) 或heapify现有列表，如下所示：

堆是二叉树，每个父节点的值都小于或等于其任何子节点。此实现使用数组 whichheap[k] <= heap[2*k+1]和heap[k] <= heap[2*k+2]for all k，从零开始计数元素。

此属性称为堆不变量。您应该注意的一件事是，在这种情况下，排序列表作为堆已经是有效的（可以很容易地观察到原因 - 因为每个项目都小于它的右邻居，所以必须如此）。堆也是平衡的，保证1所有叶子节点到根的高度之间存在最大差异，这将在后面证明。如果您的列表未排序，或者还不是堆，则必须调用heapq.heapify以获取有效堆。

>>> import heapq
>>> L = [2, 3, 1, 9, 10]
>>> heapq.heapify(L)
>>> L
[1, 3, 2, 9, 10]

作为一个堆，这现在看起来像

          1
        /   \
      3      2
    /   \
  9      10

此操作在线性时间（O(N)时间）内工作。如您所见，最小的项目始终位于0th列表的索引处。这使得检索变得简单：

>>> L[0]
1

对于最大的项目，情况并非如此。在这种情况下，您必须heapq.nlargest与n=1项目一起使用：

>>> heapq.nlargest(1, L)
[10]

要从堆中弹出一个项目，您可以使用heapq.heappop()它将从堆中弹出最小的项目。 

>>> heapq.heappop(L)
1

执行此操作的代码如下所示：

def heappop(heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
    else:
        returnitem = lastelt
    return returnitem

这样做是返回0th元素。但首先它将堆中的最后一项（heap.pop()将从列表中删除heap[-1]）与第一项（heap[0] = lastelt）交换。必须调用模块中的隐藏函数_siftup来heapq保持堆不变。出于科学目的，这是执行此操作的代码（heapq使用更快的C代码实现，但它在语义上等效之前有一个 Python 实现）：

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and not cmp_lt(heap[childpos], heap[rightpos]):
            childpos = rightpos
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

它基本上一直在用它最小的孩子交换父母。此操作需要O(log n)时间，log n即平衡二叉树的高度。要将项目添加到堆中，请使用：

>>> heapq.heappush(L, 7)
>>> L
[3, 7, 10, 9]

这需要O(log n)时间。它首先将项目附加到列表的末尾，因为这会在列表的高度添加一个新节点，比如说，h该新节点的索引将等于2*k + 1或2*k + 2，让我们假设2*k + 1某个节点在索引处的（）k与高度h - 1。因此，如果您附加另一个项目，索引将是2*k + 2，同一节点的右子节点，那么您添加的下一个索引将是另一个节点的左子节点，位于 height 的最后一个节点的右侧h - 1，这意味着树始终是平衡的. 如果您最终继续添加，您将填充该行并创建一个新行，等等。

无论如何，它会调用模块中的_siftdown隐藏函数，heapq如下所示：

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if cmp_lt(newitem, parent):
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

它基本上不断检查孩子是否小于其父母，如果是，则交换两者。由于它是一棵平衡二叉树，树的高度将是O(log n)，log n即可能需要交换的父级数量，以保持堆不变。

如果你想对 heapq 进行排序，你可以在最佳排序时间内O(N log N)使用 heapsort 进行排序，只需重复调用heappop队列即可：

[heappop(L) for i in range(len(L))]

当然，Python 的内置sorted代码比这段代码优化得多，并且执行速度更快，尽管如果你不使用 Python 并且只是说在 中实现了一个堆C，你会这样做。最后遍历堆很容易，只需遍历您的列表：

for x in L:
    print x

尽管我认为这不会是任何理想的顺序。

于 2013-04-20T02:26:00.857 回答
5

模块中的队列Queue主要用于实现多线程的生产者/消费者模式。如果您对通用优先级队列数据结构感兴趣，请使用heapq模块.

于 2013-04-19T23:53:11.903 回答
-1

您可以使用 PriorityQueue。这是示例。

In [1]: from Queue import PriorityQueue
In [2]: pq = PriorityQueue()
In [3]: pq.put((1, "girl"))    # put data in the form of tuple (priority, data)
In [4]: pq.put((3, "forest"))
In [5]: pq.put((2, "rain"))
In [6]: pq.get()               # retrieves data. lowest priority number first.
Out[6]: (1, 'girl')
In [7]: pq.empty()             # checks if empty
Out[7]: False
In [8]: pq.full()              # checks if full
Out[8]: False
In [9]: pq.qsize()             # current size of the queue.
Out[9]: 2

此外，您将能够扩展 PriorityQueue 类并自定义事物。

于 2013-04-20T02:45:20.583 回答