在python中，队列是如何工作的？

Question

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

Answer 1

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

Answer 2

Queue不是您要查找的优先级队列。你可以使用一个空列表([])或者heapify一个已有的列表，如下所示：

堆是二叉树，每个父节点的值都小于或等于它的任何一个子节点。此实现使用heap[k] <= heap[2*k+1]和heap[k] <= heap[2*k+2]表示所有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

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

>>> 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)交换。必须调用heapq模块中的隐藏函数_siftup来维护堆不变量。出于科学目的，下面是实现这一点的代码(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，即同一节点的右子节点，那么您添加的下一个索引将是高度为h - 1的最后一个节点右侧的另一个节点的左子节点，这意味着树始终是平衡的。如果您不断添加，最终将填充该行并创建一个新行，依此类推。

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

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进行排序，您可以使用heapsort在最佳排序时间O(N log N)中执行此操作，只需重复调用队列上的heappop：

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

当然，Python的内置sorted比这段代码要优化得多，执行速度也更快，尽管如果您没有使用Python，只是说用C实现了一个堆，那么您就会这么做。最后，遍历堆很简单，只需遍历列表即可：

for x in L:
    print x

虽然我认为这不会有任何令人满意的顺序。

Answer 3

你可以使用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类并对其进行自定义。