Python中的heapq优先队列

Python中的heapq优先队列

heapq 模块是 Python 标准库中用于堆（heap）数据结构的工具，一种轻量级的方式来实现优先队列（Priority Queue），也称为最小堆（Min-Heap）。优先队列是一种特殊的队列，其中每个元素都关联有一个优先级或权重，并且具有最高优先级（最小权重）的元素始终位于队列的前面。它提供了一组函数，用于在列表上执行堆操作，通常用于实现优先队列和与优先级相关的算法。

如下图，是一个heapq优先队列二叉树结构：

01

原理和特点

原理

• 堆数据结构：堆是一种特殊的树状数据结构，通常用于实现优先队列。在最小堆中，父节点的值小于或等于其子节点的值。在最大堆中，父节点的值大于或等于其子节点的值。

• 二进制堆：heapq 模块实现的是二进制堆，这是一种紧凑的数据结构，通常以列表的形式表示。它的性质是：父节点的索引 i 与其左子节点的索引 2i+1 和右子节点的索引 2i+2 之间存在特定的关系。

特点

在 heapq 中，优先队列的实现依赖于堆数据结构，因此它具有以下特点：

• 最小堆性质

  在优先队列中，具有最高优先级的元素（最小权重）始终位于队列的前面，因此可以轻松地获取并移除具有最高优先级的元素。

• 高效性能

  堆是一种高效的数据结构，插入和删除元素的时间复杂度为 O(log n)，其中 n 是队列中元素的数量。这使得优先队列非常适合需要快速访问最高优先级元素的应用。

02

常见用法

heapq.heapify(iterable) 堆排序

使用 heapify(iterable) 函数，可以将一个可迭代对象（通常是列表）转换为堆。这个函数在原地进行操作，不返回新的堆对象。

import heapq  
  
numbers = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]  
  
print(f'转换前的列表: {numbers}')  # 转换前的列表: [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]  
# 将列表转换成堆序列，不返回数据  
heapq.heapify(numbers)  
print(f'转换后的列表: {numbers}')  # 转换
1
2
3
4
5
6
7