详解 Python 标准库中的 PriorityQueue 代码实现

最编程 2024-07-19 21:23:46

...

「这是我参与2022首次更文挑战的第16天，活动详情查看：2022首次更文挑战」。

正式的Python专栏第65篇，同学站住，别错过这个从0开始的文章！

前面学委说要把内置队列都撸一撸，前面展示了有简单的先进后出，先进先出队列。

上一篇展示了优先队列在餐馆场景的展示，并且快速的讲解了优先队列出队操作背后的运算逻辑（使用二叉堆）。

优先队列的出队

大家还记得出队列的方法不？

如下图所示，这个是队列父类queue.Queue类的get方法（取出队列的元素）。

屏幕快照 2022-02-16 上午12.03.09.png

在get方法中调用了优先队列的_get方法（因为被子类PriorityQueue覆盖了）

下面是优先队列的出队操作调用的方法_get

def _get(self):
    return heappop(self.queue)

这里又是用到了二叉堆，我们继续看它的实现：

def heappop(heap):
    lastelt = heap.pop()    
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
    return lastelt

方法内：

第一行：直接从列表弹出元素（取出）。当整个优先队列取完了，这里遇到空的列表，程序马上报错。（读者可以单独生成一个list对象，直接pop。也就是'[].pop()')

第二行：继续检测列表heap（维护一个二叉堆结构）是否为空了，如果是，直接运行最后一行（返回列表最后一个元素），并且if内的语句不被执行。这种情况表示当前列表内仅有最后一个元素，这种最简单了。

否则（第三行开始），需要动态平衡二叉树，进行执行判断。这里主要分为两步：

第一步，也就是我们直接把二叉树顶部节点去掉了，最小堆顶部元素优先数值最小，优先级别最高，直接取就对的。
第二步，把顶部元素换成最后一个加入的元素，直接衔接剩下两颗子树。但此时的二叉树不是最小二叉堆，所以这里就进入了下面的方法。

为了方便解析，直接贴_siftup源码到这，读者可以快速读一下：

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

方法内前三行先确定次起始位置，上层左边元素位置（childpos），顶部元素newitem。

进入循环，这里的退出条件是左边孩子节点位置是否=>剩下列表的长度。因为每次放入元素总是从左到右依次每层放置完。

我们看看循环内部，二叉树左边节点为2pos+1，右边节点为（2pos+1）+1。

通过这行代码‘rightpos < endpos and not heap[childpos] < heap[rightpos]’ ，可以保证在边界内始终：

顶部新节点与左右节点中最小的元素进行位置置换（heap[pos] = heap[childpos]），也就是上移左右节点中较小值上升为节点根部，保证后续子树满足最小二叉堆条件。

直到没有后续叶子节点比对。这时候相当于把一侧最小值获取到，放到顶部执行_siftdown方法，这个在前篇文章解析过了。

总结

优先队列，使用了最小二叉堆为核心，实现了高效出队列和入队列。

稍后在出图展示吧，这里说的高效，主要是优先队列运用二叉树结构来处理出入队，每次不需要整个列表遍历（具体的运算效率下篇展示）。

喜欢Python的朋友，请关注学委的 Python基础专栏 or Python入门到精通大专栏

持续学习持续开发，我是雷学委！
编程很有趣，关键是把技术搞透彻讲明白。
欢迎关注微信，点赞支持收藏!

上一篇： Dijkstra算法之堆/优先队列优化实践小结

下一篇：探讨队列概念及其在广度优先搜索中的应用实例详解

详解 Python 标准库中的 PriorityQueue 代码实现

双向链表中插入函数的 C++ 标准库实现。-示例 1：

快速傅里叶变换在Python中的实现及其代码解析

Python中的颜色代码和编号详解

如何在Shopify代码库中实现多态关联的储存方法？

Java开发中的Apache Commons Lang库：StringUtils工具类详解与源代码解析

详解高斯过程中的函数最优化：从理论推导到实战实现（配代码与公式示例）