用python实现一个优先级队列?
时间: 2023-07-18 15:14:21 浏览: 52
在Python中,可以使用内置的heapq模块来实现优先级队列。heapq模块提供了一种基于堆数据结构的优先级队列实现,可以快速地插入和弹出元素,并且可以保证队列中元素的顺序是按照优先级从高到低排列的。下面是一个用Python实现优先级队列的示例代码:
```python
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]
```
在上面的代码中,我们定义了一个PriorityQueue类,它包含两个实例变量:_queue和_index。_queue是一个列表,用于保存插入的元素和它们的优先级;_index是一个计数器,用于给元素分配一个唯一的序号,以便在优先级相同时能够按照插入顺序比较它们的大小。
这个类包含两个方法:push和pop。push方法用于向队列中插入元素,它接受两个参数,一个是元素本身,另一个是元素的优先级。push方法将元素和优先级打包成一个三元组,然后使用heapq.heappush函数将这个三元组插入到_queue列表中。由于heapq默认是按照升序排序的,而我们需要按照优先级降序排序,因此需要将优先级取负数。同时,我们还需要将元素的序号加入到三元组中,以便在优先级相同时能够按照插入顺序比较它们的大小。
pop方法用于从队列中弹出元素,它使用heapq.heappop函数从_queue列表中弹出具有最高优先级的元素,并返回它的值。
使用这个PriorityQueue类,我们可以轻松地实现优先级队列,例如:
```python
q = PriorityQueue()
q.push('task1', 3)
q.push('task2', 1)
q.push('task3', 2)
print(q.pop()) # 输出:task1
print(q.pop()) # 输出:task3
print(q.pop()) # 输出:task2
```
在上面的代码中,我们向队列中插入了三个元素,它们的优先级分别是3、1和2。通过多次调用pop方法,我们可以按照优先级从高到低依次弹出元素。