博客

详解Python 优先队列

  • Post category:Python

Python 中优先队列是通过 heapq 模块实现的，可以针对不同的元素优先级建立一个堆。

基本用法

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)

print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 4

上面的例子中，我们先创建了一个空堆，然后通过 heappush 方法往堆里面添加元素。注意，优先队列的元素必须是可比较的，否则会抛出 TypeError 异常。

可以通过 heappop 方法弹出堆顶最小（或最大）元素。弹出元素后，原有堆的顺序会被重新调整。

自定义比较函数

默认情况下，Python 中的优先队列只适用于数字和字符串等内置的可比较数据类型。如果需要适用于自定义对象，需要自定义比较函数。

比较函数的返回值是两个元素是否满足优先级关系，可以通过 __lt__ 方法来实现：

class User:
    def __init__(self, name, priority):
        self.name = name
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority

heap = []
heapq.heappush(heap, User("Tom", 4))
heapq.heappush(heap, User("Alice", 1))
heapq.heappush(heap, User("John", 3))
heapq.heappush(heap, User("Bob", 2))

while heap:
    print(heapq.heappop(heap).name)

在上面的例子中，我们创建了一个自定义的 User 类，其包含一个 name 和一个 priority 成员变量。我们通过 __lt__ 方法重新定义类的大小比较规则。这样，我们就可以通过 heappush 方法往堆里面添加 User 对象了。

堆排序

Python 中的 heapq 模块可以实现堆排序。通过 heapq.heapify 方法，可以把一个无序的列表（或可迭代对象）转换成堆：

import heapq

heap = [3, 1, 4, 2]
heapq.heapify(heap)

print(heap)  # [1, 2, 4, 3]

上面的例子中，我们将列表 [3, 1, 4, 2] 转换成了一个优先队列。通过 heappop 方法，可以依次弹出堆里面的最小值（依次构成了排序后的列表）：

import heapq

heap = [3, 1, 4, 2]
heapq.heapify(heap)

sorted_list = []
while heap:
    sorted_list.append(heapq.heappop(heap))

print(sorted_list)  # [1, 2, 3, 4]

通过堆排序，我们可以快速得到一个列表的排序结果。

总结

本文主要介绍了 Python 中优先队列（堆）的使用方法。通过 heapq 模块，我们可以方便地对不同类型的元素建立不同的堆。如果需要使用自定义类，需要定义比较函数。在处理排序问题时，也可以使用 heapq 模块的排序功能进行排序。

Tags: