3.5. heapq – 堆排序算法 | 数据结构 |《python 3 标准库实例教程》| python 技术论坛-江南app体育官方入口
目的：heapq 实现了适用于 python 列表对象的最小堆排序算法。
堆是一个具有树状结构的数据结构，子节点与父节点的排序具有一定的顺序关系。 二叉堆能通过一个列表或者一个数组表示，这样对于下标为 n 的元素，它的子节点的下标就分别为 2 * n 1 和 2 * n 2（假设以 0 作为起始下标）。这种特性使得重新调整堆结构可以在原数据结构上进行，而不需要在增加和删除元素的时候额外分配大量的内存空间。
一个最大堆保证了父节点的值大于或等于子节点的值。一个最小堆则是父节点的值要小于等于子节点的值。 python 的 heapq 模块使用的是最小堆。
示例数据
这个部分的例子使用 heapq_heapdata.py 中的数据。
heapq_heapdata.py
# 下面的 data 里面的数据是由 random 模块生成的。
data = [19, 9, 4, 10, 11]
使用 heapq_showtree.py 模块来打印堆。
heapq_showtree.py
import math
from io import stringio
def show_tree(tree, total_width=36, fill=' '):
"""漂亮的打印一棵树。"""
output = stringio()
last_row = -1
for i, n in enumerate(tree):
if i:
row = int(math.floor(math.log(i 1, 2)))
else:
row = 0
if row != last_row:
output.write('\n')
columns = 2 ** row
col_width = int(math.floor(total_width / columns))
output.write(str(n).center(col_width, fill))
last_row = row
print(output.getvalue())
print('-' * total_width)
print()
创建一个堆
有两种基本的方法可以创建一个堆， 它们是 heappush() 和 heapify() 。
heapq_heappush.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
heap = []
print('random :', data)
print()
for n in data:
print('add {:>3}:'.format(n))
heapq.heappush(heap, n)
show_tree(heap)
当使用 heappush() 这个方法的时候，堆中数据的顺序会与从数据源加载进来时的数据的顺序保持一致。
$ python3 heapq_heappush.py
random : [19, 9, 4, 10, 11]
add 19:
19
------------------------------------
add 9:
9
19
------------------------------------
add 4:
4
19 9
------------------------------------
add 10:
4
10 9
19
------------------------------------
add 11:
4
10 9
19 11
------------------------------------
如果数据早就存储在内存中，使用 heapify() 方法可以更快的对列表中的数据进行原地重排。
heapq_heapify.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
print('random :', data)
heapq.heapify(data)
print('heapified :')
show_tree(data)
一次一个元素的构建堆排序的列表和对一个已有的无序列表调用 heapify() 方法的结果是完全相同的。
$ python3 heapq_heapify.py
random : [19, 9, 4, 10, 11]
heapified :
4
9 19
10 11
------------------------------------
访问堆中的元素
当堆中元素排序好之后, 使用 heappop() 方法可以移除值最小的元素。
heapq_heappop.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
print('random :', data)
heapq.heapify(data)
print('heapified :')
show_tree(data)
print()
for i in range(2):
smallest = heapq.heappop(data)
print('pop {:>3}:'.format(smallest))
show_tree(data)
在这个例子里， heapify() 和 heappop() 方法组合起来使用，可以获得一个排序好的列表。
$ python3 heapq_heappop.py
random : [19, 9, 4, 10, 11]
heapified :
4
9 19
10 11
------------------------------------
pop 4:
9
10 19
11
------------------------------------
pop 9:
10
11 19
------------------------------------
移除堆中存在的元素并替换为其他元素，可以使用方法 heapreplace() 实现。
heapq_heapreplace.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
heapq.heapify(data)
print('start:')
show_tree(data)
for n in [0, 13]:
smallest = heapq.heapreplace(data, n)
print('replace {:>2} with {:>2}:'.format(smallest, n))
show_tree(data)
原地替换元素并且维持指定大小的堆结构，可以用于实现例如优先队列这样的数据结构。
$ python3 heapq_heapreplace.py
start:
4
9 19
10 11
------------------------------------
replace 4 with 0:
0
9 19
10 11
------------------------------------
replace 0 with 13:
9
10 19
13 11
------------------------------------
从堆中抽取数据
heapq 还包含两个用于检查可迭代对象并找到它所包含的最大或最小值范围的函数。
heapq_extremes.py
import heapq
from heapq_heapdata import data
print('all :', data)
print('3 largest :', heapq.nlargest(3, data))
print('from sort :', list(reversed(sorted(data)[-3:])))
print('3 smallest:', heapq.nsmallest(3, data))
print('from sort :', sorted(data)[:3])
nlargest() 和 nsmallest() 这两个函数只对当 n > 1 并且 n 较小的时候表现出很高的效率，但是在少数情况下仍然可以派上用场。
$ python3 heapq_extremes.py
all : [19, 9, 4, 10, 11]
3 largest : [19, 11, 10]
from sort : [19, 11, 10]
3 smallest: [4, 9, 10]
from sort : [4, 9, 10]
高效合并两个已排序的列表
对于小数据集来说，将几个已排序列表组合成一个新列表是很容易的。
list(sorted(itertools.chain(*data)))
对于大数据集，上述方法会使用大量的内存。merge() 使用堆去一次生成一个新的列表 ，可以使用固定数量的内存来确定下一个元素，而不是对合并之后的列表进行整体排序。
heapq_merge.py
import heapq
import random
random.seed(2016)
data = []
for i in range(4):
new_data = list(random.sample(range(1, 101), 5))
new_data.sort()
data.append(new_data)
for i, d in enumerate(data):
print('{}: {}'.format(i, d))
print('\nmerged:')
for i in heapq.merge(*data):
print(i, end=' ')
print()
因为 merge() 方法使用堆来实现，它是根据被合并的列表的数量而不是列表中的元素数量来消耗内存的。
$ python3 heapq_merge.py
0: [33, 58, 71, 88, 95]
1: [10, 11, 17, 38, 91]
2: [13, 18, 39, 61, 63]
3: [20, 27, 31, 42, 45]
merged:
10 11 13 17 18 20 27 31 33 38 39 42 45 58 61 63 71 88 91 95
扩展阅读
- -- 对于堆数据结构的整体描述。
- -- 标准库里面的优先队列
queue的实现。
本译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 cc 协议，如果我们的工作有侵犯到您的权益，请及时联系江南app体育官方入口。
