Python优先级队列示例

  1. Python基础教程
  2. 在SublimeEditor中配置Python环境
  3. Python代码中添加注释
  4. Python中的变量的使用
  5. Python中的数据类型
  6. Python中的关键字
  7. Python字符串操作
  8. Python中的list操作
  9. Python中的Tuple操作
  10. Pythonmax（）和min（）–在列表或数组中查找最大值和最小值
  11. Python找到最大的N个（前N个）或最小的N个项目
  12. Python读写CSV文件
  13. Python中使用httplib2–HTTPGET和POST示例
  14. Python将tuple开箱为变量或参数
  15. Python开箱Tuple–太多值无法解压
  16. Pythonmultidict示例–将单个键映射到字典中的多个值
  17. PythonOrderedDict–有序字典
  18. Python字典交集–比较两个字典
  19. Python优先级队列示例
  20. python中如何格式化日期
  21. 30 分钟 Python 爬虫教程

1.什么是优先队列

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

2. Python中的优先级队列实现

以下python程序使用该heapq模块实现简单的优先级队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
PriorityQueue.py

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]

3. Python优先级队列示例

让我们看一个如何使用上面创建的优先级队列的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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

学习愉快！