本文介绍Python中优先队列的用法
- 注意:
queue并不能算是Python标准库,所以在LeetCode等OJ环境中不能使用, 想要使用优先队列的话可以使用Python的标准库heapq heapq的使用请参考 Python——heapq模块-最大堆最小堆
导入包
1 | from Queue import PriorityQueue |
queue包名已经弃用,测试发现本地Python2.7环境可以用,但是LeetCode线上环境不能用- 推荐使用
Queue
使用
1 | from Queue import PriorityQueue |
不能使用
not pq这样的语句判断优先队列是否收敛,他不是普通的内嵌对象(list,str等是内嵌对象),除非pq == None否则,双端队列对象永远为not pq == False下面用法最优:
1
while pq.qsize():
PriorityQueue中默认递增排序(这一点与Python中的sorted函数和sort()函数一样),每次get(),移除并返回最小的对象
PriorityQueue中,可以同时添加不同类别的对象
PriorityQueue会将对象首先按照类别排序,然后各个类别内部按照不同数值排序
若传入对象是可以直接比较大小的类型即可直接传入,包括tuple, list, str, int(long)等类型
- Python中list,tuple,str等都是可以直接比较大小的,默认使用他们的第一个元素比较大小,如果第一个元素相等,则比较第二个元素,以此类推
- 详细情况参考本文后面的说明
Python中的内嵌对象比较大小
- Python中类别间也可以比较大小,默认类别间大小为:tuple > str > list > int(long) > None, 但是记不清楚的话不建议使用Python的这个特性,容易造成错误
- Python中list,tuple,str等都是可以直接比较大小的,默认使用他们的第一个元素比较大小,如果第一个元素相等,则比较第二个元素,以此类推
- Python中类别间也可以比较大小,默认类别间大小为:tuple > str > list > int(long) > None, 但是记不清楚的话不建议使用Python的这个特性,容易造成错误
1
2
3
4
5ls = [(1, 'b'), (1, 'a'), (2, 'a'), [1, 'a'], [1, 'b'], [2, 'a'], '1a', '1b', '2a', 1, 2, 3, None]
ls.sort()
print ls
# output
[None, 1, 2, 3, [1, 'a'], [1, 'b'], [2, 'a'], '1a', '1b', '2a', (1, 'a'), (1, 'b'), (2, 'a')]
Python自定义对象比较大小
在做算法题时,没必要的情况下不建议使用
在做工程时建议使用这种方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17import Queue
class Node():
def __init__(self, val):
self.val = val
def __lt__(self, other):
return self.val < other.val
pq = Queue.PriorityQueue()
pq.put(Node(5))
pq.put(Node(1))
while pq.qsize():
print pq.get().val
# output
1
5注意
__lt__函数中是小于号,说明递增排序,大于号,说明递减排序PriorityQueue对象不是普通Python内嵌对象,不能使用Python内嵌的
len函数
