python内置堆如何实现

您所在的位置：网站首页 › 字典进行排序怎么操作 › python内置堆如何实现

python内置堆如何实现

2023-05-01 18:02| 来源: 网络整理| 查看: 265

1.简介

堆，又称优先队列，是一个完全二叉树，它的每个父节点的值都只会小于或等于所有孩子节点（的值）。它使用了数组来实现：从零开始计数，对于所有的 k ，都有 heap[k] 5，交换7和5

python内置堆如何实现

5.符合堆的要求，即结果为[2, 5, 3, 7]

原有数据不是堆

import heapq h = [5, 2, 1, 4, 7] heapq.heappop(h) print(h) [1, 2, 7, 4]登录后复制

操作流程如下：

1.初始状态，很明显不符合堆的性质

python内置堆如何实现

2.移除最上面的元素（第一个元素）,重新对剩下的元素进行堆的排列

python内置堆如何实现

3.依据python最小堆的特性，2>1 交换2与1

python内置堆如何实现

4.符合堆的要求，结果为[1, 2, 7, 4]

heapq.heappushpop(heap, item)

将 item 放入堆中，然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。需要注意的是弹出的元素必须位于堆顶或者堆尾，也就是说当插入一个元素后，进行比较最小元素时，其实一直比较的都是堆顶元素，如果插入元素大于或等于堆顶元素，则堆不会发生变化，当插入元素小于堆顶元素，则堆会依据python堆的最小堆特性进行处理。

原有数据是堆

import heapq h = [1, 2, 3, 5, 7] min_data = heapq.heappushpop(h, 2) print(min_data) print(h) #输出 1 [2, 2, 3, 5, 7]登录后复制

操作流程如下

1.初始状态

python内置堆如何实现

2.插入元素2

python内置堆如何实现

3.删除最小元素，刚好是堆顶元素1，并使用末尾元素2代替

python内置堆如何实现

4.符合要求，即结果为[2, 2, 3, 5, 7]

原有数据不是堆

h = [5, 2, 1, 4, 7] min_data = heapq.heappushpop(h, 2) print(min_data) print(h) min_data = heapq.heappushpop(h, 6) print(min_data) print(h) #输出 2 [5, 2, 1, 4, 7] 5 [1, 2, 6, 4, 7]登录后复制

对于插入元素6的操作过程如下

1.初始状态

python内置堆如何实现

2.插入元素6之后

python内置堆如何实现

3.发现元素6大于堆顶元素5，弹出堆顶元素5，由堆尾元素6替换

python内置堆如何实现

4.依据python的最小堆特性，元素6>元素1且元素6>元素2，但元素2>元素1，交换6与1

python内置堆如何实现

5.符合要求，则结果为[1, 2, 6, 4, 7]

由结果可以看出，当插入元素小于堆顶元素时，则堆不会发生改变，当插入元素大于堆顶元素时，则堆依据python堆的最小堆特性处理。

heapq.heapify(x)

将列表转换为堆。

h = [1, 2, 3, 5, 7] heapq.heapify(h) print(h) h = [5, 2, 1, 4, 7] heapq.heapify(h) print(h) #输出 [1, 2, 3, 5, 7] [1, 2, 5, 4, 7]登录后复制

会自动将列表依据python最小堆特性进行重新排列。

heapq.heapreplace(heap, item)

弹出并返回最小的元素，并且添加一个新元素item，这个单步骤操作比heappop()加heappush() 更高效。适用于堆元素数量固定的情况。

返回的值可能会比添加的 item 更大。如果不希望如此，可考虑改用heappushpop()。它的 push/pop 组合会返回两个值中较小的一个，将较大的值留在堆中。

import heapq h = [1, 2, 3, 5, 7] heapq.heapreplace(h, 6) print(h) h = [5, 2, 1, 4, 7] heapq.heapreplace(h, 6) print(h) #输出 [2, 5, 3, 6, 7] [1, 2, 6, 4, 7]登录后复制

原有数据是堆

对于插入元素6的操作过程如下：

1.初始状态

python内置堆如何实现

2.弹出最小元素，只能弹出堆顶或者堆尾的元素，很明显，最小元素是1，弹出1，插入元素是6，代替堆顶元素

python内置堆如何实现

3.依据python堆的最小堆特性，6>2,交换6与2

python内置堆如何实现

4.依据python堆的最小堆特性，6>5,交换6与5

python内置堆如何实现

5.符合要求，则结果为[2, 5, 3, 6 ,7]

原有数据不是堆

对于插入元素6的操作过程如下：

1.初始状态

python内置堆如何实现

2.对于数据不为堆的情况下，默认移除第一个元素，这里就是元素5，然后插入元素6到堆顶

python内置堆如何实现

3.依据python的最小堆特性，元素6>1,交换元素6与1

python内置堆如何实现

4.符合要求，即结果为[1, 2, 6, 4, 7

heapq.merge(*iterables, key=None, reverse=False)

将多个已排序的输入合并为一个已排序的输出（例如，合并来自多个日志文件的带时间戳的条目）。返回已排序值的 iterator。注意需要是已排序完成的可迭代对象（默认为从小到大排序），当reverse为True时，则为从大到小排序。

heapq.nlargest(n, iterable, key=None)

从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。

等价于: sorted(iterable, key=key, reverse=True)[:n]。

import time import heapq h = [1, 2, 3, 5, 7] size = 1000000 start = time.time() print(heapq.nlargest(3, h)) for i in range(size): heapq.nlargest(3, h) print(time.time() - start) start = time.time() print(sorted(h, reverse=True)[:3:]) for i in range(size): sorted(h, reverse=True)[:3:] print(time.time() - start) #输出 [7, 5, 3] 1.6576552391052246 [7, 5, 3] 0.2772986888885498 [7, 5, 4]登录后复制

由上述结构可见，heapq.nlargest与sorted(iterable, key=key, reverse=False)[:n]功能是类似的，但是性能方面还是sorted较为快速。

heapq.nsmallest(n, iterable, key=None)

从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。等价于: sorted(iterable, key=key)[:n]。

import time import heapq h = [1, 2, 3, 5, 7] size = 1000000 start = time.time() print(heapq.nsmallest(3, h)) for i in range(size): heapq.nsmallest(2, h) print(time.time() - start) start = time.time() print(sorted(h, reverse=False)[:3:]) for i in range(size): sorted(h, reverse=False)[:2:] print(time.time() - start) #输出 [1, 2, 3] 1.1738648414611816 [1, 2, 3] 0.2871997356414795登录后复制

由上述结果可见，sorted的性能比后面两个函数都要好，但如果只是返回最大的或者最小的一个元素，则使用max和min最好。

3.堆排序

由于在python中堆的特性是最小堆，堆顶的元素始终是最小的，可以将序列转换成堆之后，再使用pop弹出堆顶元素来实现从小到大排序。具体实现如下：

from heapq import heappush, heappop, heapify def heapsort(iterable): h = [] for value in iterable: heappush(h, value) return [heappop(h) for i in range(len(h))] def heapsort2(iterable): heapify(iterable) return [heappop(iterable) for i in range(len(iterable))] data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] print(heapsort(data)) print(heapsort2(data)) #输出 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]登录后复制4.堆中元素可以是元组形式，主要用于任务优先级from heapq import heappush, heappop h = [] heappush(h, (5, 'write code')) heappush(h, (7, 'release product')) heappush(h, (1, 'write spec')) heappush(h, (3, 'create tests')) print(h) print(heappop(h)) [(1, 'write spec'), (3, 'create tests'), (5, 'write code'), (7, 'release product')] (1, 'write spec')登录后复制

上述操作流程如下：

1.当进行第一次push(5, ‘write code’)时

python内置堆如何实现