跳转至

Python 优先队列

PriorityQueue基本使用

直接见代码如下

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

# 初始化
pq = PriorityQueue()

# 判断是否为空
assert pq.empty() is True

# 新增元素，元祖形式放入队列，元祖第一个元素为优先级，数值越小优先级越高
pq.put((0, 2))
pq.put((0, 1))
pq.put((1, 1))
pq.put((1, 2))
pq.put((2, 2))
pq.put((2, 1))

# 获取队列长度
pq_size = pq.qsize()  # 6
print(pq_size)

# 取出元素
while not pq.empty():
    x = pq.get()
    print(x)

# 结果如下：首先从优先级高的取，然后比较同优先级的数值小的优先取出来
# (0, 1)
# (0, 2)
# (1, 1)
# (1, 2)
# (2, 1)
# (2, 2)

PriorityQueue放入自定义对象

如果是自定义的类对象，无法直接比较大小，此时需要自定义这个类的小于号操作符，即重载<，示例如下

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


class MyObject(object):
    def __init__(self, value: str):
        self.value = value

    def __lt__(self, other):
        """利用value的字符串长度作为类的比较大小基准"""
        return len(self.value) < len(other.value)


pq = PriorityQueue()

my_obj_1 = MyObject('wonderful')
my_obj_2 = MyObject('world')

pq.put((1, my_obj_1))
pq.put((1, my_obj_2))

while not pq.empty():
    priority, data = pq.get()
    print(data.value)

# 结果如下
# world
# wonderful

参考