队列如何在python中工作？

Question

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

Answer 1

Queue不是您要查找的优先级队列.相反,你正在寻找heapq,适用于Python list.您可以使用空列表([])或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

对于最大的项目,情况并非如此.在这种情况下,你必须使用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该同一节点的右子项,那么您添加的下一个索引将是最后一个高度右侧的另一个节点的左子节点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

虽然我认为这不会是任何理想的顺序.

Answer 2

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