python模块之heapq

心在远方AND走在路上 2021-08-10

1414

一、导言

heapq模块用于实现一个适合与Python的列表一起使用的最小堆排序算法

1、二叉树

1）、树中每个节点至多有两个子节点

2）、满二叉树

树中除了叶子节点，每个节点都有两个子节点

3）、什么是完全二叉树

在满足满二叉树的性质后，最后一层的叶子节点均需在最左边

2、堆是什么？

答：堆是一种数据结构，它是一颗完全二叉树。最小堆则是在堆的基础增加了新的规则，它的根结点的值是最小的，而且它的任意结点的父结点的值都小于或者等于其左右结点的值。因为二进制堆可以使用有组织的列表或数组来表示，所以元素N的子元素位于位置2 * N + 1和2 * N + 2。这种布局使重新安排堆成为可能，因此在添加或删除项时不需要重新分配那么多内存

区分堆(heap)与栈(stack)：堆与二叉树有关，像一堆金字塔型泥沙；而栈像一个直立垃圾桶，一列下来。

1）、最大堆

最大堆确保父堆大于或等于它的两个子堆。

2）、最小堆

最小堆要求父堆小于或等于其子堆。Python的heapq模块实现了一个最小堆。

二、使用案例

1、创建一个堆

# This data was generated with the random module.
data = [19, 9, 4, 10, 11]
import math
from io import StringIO
def show_tree(tree, total_width=36, fill=' '):
    """Pretty-print a tree."""
    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)

创建一个堆方案一：

heappush()

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()时，当从数据源添加新项时，将维护元素的堆排序顺序。

运行结果：

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【若数据已经在内存中，那么使用heapify()重新排列列表中的项会更有效】

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()相同。

运行结果：

random    : [19, 9, 4, 10, 11]
heapified :
                 4
        9                 19
    10       11
------------------------------------

2、访问堆的内容

使用heappop()弹出并返回堆中的最小项，保持堆不变。如果堆是空的，则引发IndexError。

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()用于对数字列表进行排序。

random    : [19, 9, 4, 10, 11]
heapified :
                 4
        9                 19
    10       11
------------------------------------
pop      4:
                 9
        10                19
    11
------------------------------------
pop      9:
                 10
        11                19
------------------------------------

3、若是删除现有元素并用单个操作中的新值替换它们，请使用heapreplace()。

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)

替换适当的元素可以维护固定大小的堆，比如按优先级排序的作业队列。

运行结果：

start:
                 4
        9                 19
    10       11
------------------------------------
replace  4 with  0:
                 0
        9                 19
    10       11
------------------------------------
replace  0 with 13:
                9
        10                19
    13       11
------------------------------------

4、堆中的数据极端值

heapq还包含两个函数，用于检查一个迭代器，并找到它所包含的最大或最小值的范围。

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的相对较小的值有效，但在少数情况下仍然可以派上用场。

运行结果：

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]

5、有效地合并排序Sequences

对于小数据集来说，将几个排序的序列组合成一个新的序列是很容易的。

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()的实现使用堆，所以它根据要合并的序列的数量而不是这些序列中的项的数量来消耗内存。

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

上面是小根堆的相关操作。python的heapq不支持大根堆，在stackoverflow上看到了一个巧妙的实现：我们还是用小根堆来进行逻辑操作，在做push的时候，我们把最大数的相反数存进去，那么它的相反数就是最小数，仍然是堆顶元素，在访问堆顶的时候，再对它取反，就获取到了最大数。思路很是巧妙。下面是实现代码

class BigHeap:
    def init(self):
        self.arr = list()
    def heap_insert(self, val):
        heapq.heappush(self.arr, -val)
    def heapify(self):
        heapq.heapify(self.arr)
    def heap_pop(self):
        return -heapq.heappop(self.arr)
    def get_top(self):
        if not self.arr:
            return
        return -self.arr[0]

6、heapq 模块还有一个heapq.merge(*iterables) 方法，用于合并多个排序后的序列成一个排序后的序列，返回排序后的值的迭代器。

类似于sorted(itertools.chain(*iterables))，但返回的是可迭代的。

import heapq
num1 = [32, 3, 5, 34, 54, 23, 132]
num2 = [23, 2, 12, 656, 324, 23, 54]
num1 = sorted(num1)
num2 = sorted(num2)
res = heapq.merge(num1, num2)
print(list(res))

运行结果

[2, 3, 5, 12, 23, 23, 23, 32, 34, 54, 54, 132, 324, 656]

7、获取堆最大或最小值

如果需要获取堆中最大或最小的范围值，则可以使用heapq.nlargest() 或heapq.nsmallest() 函数

import heapq
nums = [1, 3, 4, 5, 2]
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))

运行结果:

[5, 4, 3]
[1, 2, 3]

这两个函数还接受一个key参数，用于dict或其他数据结构类型使用

import heapq
from pprint import pprint
portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
pprint(cheap)
pprint(expensive)

运行结果：

[{'name': 'YHOO', 'price': 16.35, 'shares': 45},
 {'name': 'FB', 'price': 21.09, 'shares': 200},
 {'name': 'HPQ', 'price': 31.75, 'shares': 35}]
[{'name': 'AAPL', 'price': 543.22, 'shares': 50},
 {'name': 'ACME', 'price': 115.65, 'shares': 75},
 {'name': 'IBM', 'price': 91.1, 'shares': 100}]

三、heapq源码

def nlargest(n, iterable, key=None):
    """Find the n largest elements in a dataset.【查找数据集中的n个元素】
    Equivalent【等价于】 to:  sorted(iterable, key=key, reverse=True)[:n]
    """
    # Short-cut for n==1 is to use max()
    if n == 1:
        it = iter(iterable)
        sentinel = object()
        result = max(it, default=sentinel, key=key)
        return [] if result is sentinel else [result]
    # sentinel 标记  faster 快速地 iterable 快速迭代 
    # When n>=size, it's faster to use sorted()
    try:
        size = len(iterable)
    except (TypeError, AttributeError):
        pass
    else:
        if n >= size:
            return sorted(iterable, key=key, reverse=True)[:n]


    # When key is none, use simpler decoration   简单装饰器
    if key is None:
        it = iter(iterable)
        result = [(elem, i) for i, elem in zip(range(0, -n, -1), it)]
        if not result:
            return result
        heapify(result)
        top = result[0][0]
        order = -n
        _heapreplace = heapreplace
        for elem in it:
            if top < elem:
                _heapreplace(result, (elem, order))
                top, _order = result[0]
                order -= 1
        result.sort(reverse=True)
        return [elem for (elem, order) in result]


    # General case, slowest method
    it = iter(iterable)
    result = [(key(elem), i, elem) for i, elem in zip(range(0, -n, -1), it)]
    if not result:
        return result
    heapify(result)
    top = result[0][0]
    order = -n
    _heapreplace = heapreplace
    for elem in it:
        k = key(elem)
        if top < k:
            _heapreplace(result, (k, order, elem))
            top, _order, _elem = result[0]
            order -= 1
    result.sort(reverse=True)
    return [elem for (k, order, elem) in result]

python

文章转载自心在远方AND走在路上，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

python模块之heapq

一、导言

1、二叉树

2、堆是什么？

二、使用案例

1、创建一个堆

创建一个堆方案一：

创建一个堆方案二：

2、访问堆的内容

3、若是删除现有元素并用单个操作中的新值替换它们，请使用heapreplace()。

4、堆中的数据极端值

5、有效地合并排序Sequences

6、heapq 模块还有一个heapq.merge(*iterables) 方法，用于合并多个排序后的序列成一个排序后的序列， 返回排序后的值的迭代器。

评论

6、heapq 模块还有一个heapq.merge(*iterables) 方法，用于合并多个排序后的序列成一个排序后的序列，返回排序后的值的迭代器。