3.5. heapq – 堆排序算法

未匹配的标注

目的: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

扩展阅读

本文章首发在 LearnKu.com 网站上。

本译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。

原文地址:https://learnku.com/docs/pymotw/heapq-he...

译文地址:https://learnku.com/docs/pymotw/heapq-he...

上一篇 下一篇
讨论数量: 0
发起讨论 只看当前版本


暂无话题~