Python优先级队列示例

系列教程导航

什么是优先队列

优先级队列（Priority Queue）是一种抽象数据类型，类似于常规队列（Queue）或堆栈（Stack）数据结构，但每个元素还具有与之关联的“优先级”。
在优先级队列中，优先级高的元素会先于优先级低的元素被处理。
如果两个元素具有相同的优先级，则将根据其进入队列的先后顺序（FIFO）为其提供服务。

Python 中的优先级队列实现

以下 Python 程序使用标准库 heapq 模块实现了一个简单的优先级队列。

实现细节说明：
heapq 实现的是小顶堆（Min-Heap），默认弹出最小值。为了实现“优先级越高越先出队”，我们将优先级取负数（-priority）存入堆中。
引入 _index 索引是为了确保当优先级相同时，先入队的元素先出队（稳定性），同时也避免了直接比较 item 对象可能引发的类型错误。

# PriorityQueue.py
import heapq

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

    def push(self, item, priority):
        # 使用元组 (-priority, index, item) 存储
        # 负优先级确保高优先级数值排在堆顶
        # index 确保同优先级下的插入顺序
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        # 返回元组中的最后一个元素，即 item
        return heapq.heappop(self._queue)[-1]

Python 优先级队列示例

让我们通过一个具体的例子来演示如何使用上面创建的优先级队列。

# example.py
class Item:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

# 交互式命令行示例
>>> q = PriorityQueue()

>>> q.push(Item('how'), 1)

>>> q.push(Item('to'), 5)

>>> q.push(Item('do'), 4)

>>> q.push(Item('in'), 2)

>>> q.push(Item('java'), 1)

>>> q.pop()
Item('to')  # 优先级 5

>>> q.pop()
Item('do')  # 优先级 4

>>> q.pop()
Item('in')  # 优先级 2

>>> q.pop()
Item('how')  # 优先级 1 (先入队)

>>> q.pop()
Item('java') # 优先级 1 (后入队)

从输出结果可以看出，元素严格按照优先级从高到低出队。对于优先级相同的元素（如 'how' 和 'java' 优先级均为 1），则按照入队顺序依次出队。

学习愉快！

说明：本文示例基于 Python 3 标准库 heapq 实现，适用于大多数 Python 3 环境。

本文地址：https://1diff.fun/archives/python-you-xian-ji-dui-lie-shi-li.html

如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。

Python优先级队列示例

系列教程导航

什么是优先队列

Python 中的优先级队列实现

Python 优先级队列示例

发表评论

表情类型

目录