Python优先级队列|极客教程

Python优先级队列

在计算机科学中，优先级队列是一种特殊的数据结构，其中每个元素都有一个优先级。常见的使用场景是任务调度、图搜索算法等需要按照优先级顺序处理的问题。Python提供了多种实现优先级队列的方式，本文将介绍常用的几种方法。

1. 使用heapq模块实现优先级队列

Python标准库中的heapq模块提供了用于堆排序的函数，可以很方便地实现优先级队列。下面是一个简单的示例代码：

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]

# 创建一个优先级队列
pq = PriorityQueue()
pq.push('geek-docs.com', 5)
pq.push('python', 3)
pq.push('priority', 7)

# 弹出元素
print(pq.pop())
print(pq.pop())
print(pq.pop())

运行结果：

priority
geek-docs.com
python

2. 使用queue.PriorityQueue类实现优先级队列

Python标准库中的queue模块提供了线程安全的队列实现，其中包含PriorityQueue类用于实现优先级队列。下面是一个示例代码：

import queue

# 创建一个优先级队列
pq = queue.PriorityQueue()

pq.put((5, 'geek-docs.com'))
pq.put((3, 'python'))
pq.put((7, 'priority'))

# 获取队列中的元素
print(pq.get())
print(pq.get())
print(pq.get())

运行结果：

(3, 'python')
(5, 'geek-docs.com')
(7, 'priority')

3. 使用sortedcontainers模块实现优先级队列

sortedcontainers是一个高效的Python模块，提供了SortedDict、SortedList等数据结构的实现。我们可以利用SortedDict实现自定义优先级队列。下面是一个示例代码：

from sortedcontainers import SortedDict

class PriorityQueue:
    def __init__(self):
        self._queue = SortedDict()

    def push(self, item, priority):
        self._queue[priority] = item

    def pop(self):
        priority, item = self._queue.popitem(index=0)
        return item

# 创建一个优先级队列
pq = PriorityQueue()
pq.push('geek-docs.com', 5)
pq.push('python', 3)
pq.push('priority', 7)

# 弹出元素
print(pq.pop())
print(pq.pop())
print(pq.pop())

运行结果：