问

看Python cookbook时有个疑惑，有关heapq的优先级队列

kenvilen_106 发布于 2022-11-06 06:08

heap

1.下面是cookbook的原代码，利用heapq模块实现了一个优先级队列，每次pop函数优先级高的被删除并返回。

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

使用方式：

>>> class Item:
...     def __init__(self, name):
...         self.name = name
...     def __repr__(self):
...         return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')

那么，问题来了，heappop（）函数会优先删除第一个元素，然后才是删除最小的元素，按照上面的使用，应该优先删除foo，然后才是最小的bar吧？这段代码是从哪里将它进行排序了么？
下面是普通的例子：

In [1]: x = [(-1, 0, 'for'), (-5, 1, 'bar'), (-4, 2, 'spam'), (-1, 3, 'grok')]

In [2]: import heapq

In [3]: heapq.heappop(x)[-1]
Out[3]: 'for'

In [4]: heapq.heappop(x)[-1]
Out[4]: 'bar'

In [5]: heapq.heappop(x)[-1]
Out[5]: 'spam'

In [6]: heapq.heappop(x)[-1]
Out[6]: 'grok'

我的背景是自学 + google，基本功不扎实，还请赐教。

2 个回答

首先，多谢 @Yushneng 的不吝赐教，查了下heappush的源码，总结下大概实现了以下的几个步骤：
1.将newitem appen进 heap里（这里的heap貌似可以是个列表，下面copy部分代码做了个小的实践）。
2.调用了_siftdown()函数，下面有源码，将newitem和父item进行了比较（源码定义了parent是newitem的位置-1然后向右位移1位，还不太理解这步骤操作，但是最终是产生了一个二叉树的结构。），此步骤保证了第一个元素必然是最小的（要是我只能想到sorted(),汗颜！）
下面是copy了两个函数，做了个实践，再次感谢 @Yushneng 。（自学编程，对于二叉树这种数据结构也是不太理解，还需要在看看。）

# _*_ coding:utf-8 _*_
#堆排序算法实例，摘自heapq库的一个函数，被用在heappush()等函数。

import heapq
import random

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

def cmp_lt(x, y):
    # Use __lt__ if available; otherwise, try __le__.
    # In Py3.x, only __lt__ will be called.
    return (x < y) if hasattr(x, '__lt__') else (not y <= x)

# x = [10,2,9,8,11,3,4,1,5,23]
#print(type(heapq.heapify(x)))
x = []
for _ in range(10):
    i = random.randrange(100)
    x.append(i)
    siftdown(x, 0, len(x)-1)
    print(x)

2022-11-12 01:53 回答

陌-天佑_807

你的例子里缺了一步：
```
heapq.heapify(x)
```
书中的例子里每一步 heappush() 都会进行排序。
2022-11-12 01:53 回答

sdfsadfwforever

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签