Python——优先队列PriorityQueue

Posted on

本文介绍Python中优先队列的用法

  • 注意: queue并不能算是Python标准库,所以在LeetCode等OJ环境中不能使用, 想要使用优先队列的话可以使用Python的标准库heapq
  • heapq的使用请参考 Python——heapq模块-最大堆最小堆

导入包

1
2
3
from Queue import PriorityQueue
# or
from queue import PriorityQueue
  • queue包名已经弃用,测试发现本地Python2.7环境可以用,但是LeetCode线上环境不能用
  • 推荐使用Queue

使用

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
from Queue import PriorityQueue

pq = PriorityQueue()

pq.put((10, "start"))
pq.put((5, "b", 12, 123))
pq.put((5, "a", 6))
pq.put(1)
pq.put(4)
pq.put([0, "a"])
pq.put([8, "b"])
pq.put("avb")
pq.put(None)

# while pq.not_empty()
# while not pq.empty()
while pq.qsize():
    print pq.get()
# output:
None
1
4
[0, 'a']
[8, 'b']
avb
(5, 'a', 6)
(5, 'b', 12, 123)
(10, 'start')

  • 不能使用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
    5
    ls = [(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
    17
    import 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函数