学习 Python 中的优先级队列

一. 什么是优先队列？

优先队列是一种特殊类型的队列，每个元素都有一个与之关联的优先级。在这个队列中，优先级高的元素会在优先级低的元素之前被出队。如果两个元素具有相同的优先级，则根据它们在队列中的顺序进行处理。

与普通队列的FIFO（先进先出）原则不同，优先队列允许根据优先级决定处理顺序。

二. 自定义优先队列的实现

我们将使用 Python 自定义一个优先队列。以下是实现代码：

class PriorityQueue:
    def __init__(self):
        # 初始化队列，包含一些初始值
        self.nums = [6, 7, 9, 4, 3, 5, 8, 10, 1]

    def add(self, val):
        # 向队列中添加新值
        self.nums.append(val)

    def isEmpty(self):
        # 检查队列是否为空
        return len(self.nums) == 0

    def delete(self):
        try:
            maxVal = 0
            # 遍历队列以找到优先级最高的元素
            for i in range(len(self.nums)):
                if self.nums[i] < self.nums[maxVal]:
                    maxVal = i

            item = self.nums[maxVal]
            # 从队列中移除该元素
            self.nums.remove(item)
            return item
        except IndexError:
            print("队列已空，无法删除元素。")
            exit()

# 测试优先队列
myQueue = PriorityQueue()
myQueue.add(12)
myQueue.add(1)
myQueue.add(14)
myQueue.add(7)
print(myQueue.nums)   # 输出：[6, 7, 9, 4, 3, 5, 8, 10, 1, 12, 1, 14, 7]
print("=======")
while not myQueue.isEmpty():
    print(myQueue.delete())

输出结果

该代码段通过自定义的优先队列实现了元素的添加和删除。

三. Heapq 数据结构

Python 提供了一个名为 heapq 的模块，支持高效的优先队列实现。它使用堆数据结构，具有以下特性：每次弹出时，返回最小的堆元素（最小堆）。在插入或弹出元素时，堆的结构将保持不变。

以下是使用 heapq 实现优先队列的示例代码：

import heapq

class HeapQExample:
    def __init__(self):
        # 初始化队列，包含一些初始值
        self.nums = [6, 7, 9, 4, 3, 5, 8, 10, 1]
        # 将列表转化为堆结构
        heapq.heapify(self.nums)

    def displayHeap(self):
        # 显示堆中所有元素
        for item in self.nums:
            print(item)

    def isEmpty(self):
        # 检查堆是否为空
        return len(self.nums) == 0

    def addToHeap(self, value):
        # 将新值添加到堆中
        heapq.heappush(self.nums, value)

    def getSmallesValue(self):
        # 获取并删除堆中最小的值
        return heapq.heappop(self.nums)

    def popAllElements(self):
        # 逐个弹出堆中所有元素
        while not self.isEmpty():
            print(self.getSmallesValue())

    def getNSmallestItems(self, n):
        # 获取堆中前n个最小元素
        return heapq.nsmallest(n, self.nums)

    def getNLargestItems(self, n):
        # 获取堆中前n个最大元素
        return heapq.nlargest(n, self.nums)

    def pushPopExample(self, val):
        # 同时执行推入和弹出操作
        return heapq.heappushpop(self.nums, val)

    def replaceExample(self, val):
        # 替换堆中最小的值并返回该值
        return heapq.heapreplace(self.nums, val)

# 测试堆队列
hqe = HeapQExample()

hqe.displayHeap()
hqe.addToHeap(11)
print('======')
hqe.displayHeap()
print('=======')
item = hqe.getSmallesValue()
print(item)    # 输出：1

print(hqe.getNSmallestItems(3)) # 输出：[1, 3, 4]
print(hqe.getNLargestItems(3)) # 输出：[11, 10, 9]
print(hqe.pushPopExample(-1))   # 输出：-1
print(hqe.replaceExample(-1))  # 输出：1

方法说明

1. heappush(heap, ele): 将指定元素插入堆中，并保持堆结构。
2. heappop(heap): 从堆中移除并返回最小元素，同时保持堆结构。
3. heappushpop(heap, ele): 将元素插入堆中，并立即弹出最小元素，效率更高。
4. heapreplace(heap, ele): 从堆中弹出最小元素，并插入新元素，返回被弹出的最小值。
5. nlargest(k, iterable, key): 返回可迭代对象中前k个最大元素。
6. nsmallest(k, iterable, key): 返回可迭代对象中前k个最小元素。

四. 总结

通过使用 Python 的 heapq 模块，可以高效地实现优先队列。相比于手动实现，使用 heapq 模块能够更快地进行元素的插入和删除操作，尤其是在处理大数据集时。这种优先队列在很多算法中都非常有用，例如 Dijkstra 算法和 Huffman 编码等。