>>> from env_helper import info; info()
页面更新时间： 2024-01-20 22:45:14
运行环境：
Linux发行版本: Debian GNU/Linux 12 (bookworm)
操作系统内核: Linux-6.1.0-17-amd64-x86_64-with-glibc2.36
Python版本: 3.11.2
10.3. Python中的堆和双端队列模块¶
在Python中，短语“开箱即用”（batteries included）最初是由Frank Stajano提出的，指的是Python丰富的标准库。 安装Python后，你就免费获得了大量很有用的模块。 鉴于有很多方式可以获取有关这些模块的详细信息，这里不打算提供完整的参考手册，而只是描述几个我喜欢的标准模块，以激发你的探索兴趣。
有用的数据结构有很多。Python支持一些较常用的，其中的字典（散列表）和列表（动态数 组）是Python语言的有机组成部分。 还有一些虽然不那么重要，但有时也能派上用场。 数据结构模块。
10.3.1. 堆¶
一种著名的数据结构是堆（heap），它是一种优先队列。优先队列让你能够以任意顺序添 加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min， 这样做的效率要高得多。
实际上，Python没有独立的堆类型，而只有一个包含一些堆操作函数的模块。 这个模块名为 heapq（其中的q表示队列），它包含6个函数，其中前4个与堆操作直接相关。 必须使用列表来表示堆对象本身。
模块heapq中一些重要的函数
函 数 |
描 述 |
|---|---|
heappush(heap, x) |
将x压入堆中 |
heappop(heap) |
从堆中弹出最小的元素 |
heapify(heap) |
让列表具备堆特征 |
heapreplace(heap, x) |
弹出最小的元素，并将x压入堆中 |
nlargest(n, iter) |
返回iter中n个最大的元素 |
nsmallest(n, iter) |
返回iter中n个最小的元素 |
函数 heappush
用于在堆中添加一个元素。请注意，不能将它用于普通列表，而只能用于使用
各种堆函数创建的列表。原因是元素的顺序很重要（虽然元素的排列顺序看起来有点随意，并没有严格地排序）。
>>> from heapq import *
>>> from random import shuffle
>>> data = list(range(10))
>>> shuffle(data)
>>> heap = []
>>> for n in data:
>>> heappush(heap, n)
>>> heap
[0, 1, 2, 4, 5, 3, 9, 7, 6, 8]
>>> heappush(heap, 0.5)
>>> heap
[0, 0.5, 2, 4, 1, 3, 9, 7, 6, 8, 5]
元素的排列顺序并不像看起来那么随意。
它们虽然不是严格排序的，但必须保证一点：位置 i 处的元素总是大于位置
i//2 处的元素（反过来说就是小于位置 2*i和 2*i+1
处的元素）。 这是底层堆算法的基础，称为堆特征（heap property）。
函数 heappop() 弹出最小的元素（总是位于索引 0
处），并确保剩余元素中最小的那个位于索引 0 处（保持堆特征）。
虽然弹出列表中第一个元素的效率通常不是很高，但这不是问题，因为
heappop() 会在幕后做些巧妙的移位操作。
>>> heappop(heap)
0
>>> heappop(heap)
0.5
>>> heappop(heap)
1
>>> heap
[2, 4, 3, 6, 5, 8, 9, 7]
函数 heapify()
通过执行尽可能少的移位操作将列表变成合法的堆（即具备堆特征）。
如果你的堆并不是使用 heappush() 创建的，应在使用 heappush() 和
heappop() 之前使用这个函数。
>>> heap = [5, 8, 0, 3, 6, 7, 9, 1, 4, 2]
>>> heapify(heap)
>>> heap
[0, 1, 5, 3, 2, 7, 9, 8, 4, 6]
函数 heapreplace()
用得没有其他函数那么多。它从堆中弹出最小的元素，再压入一个新元素。
相比于依次执行函数 heappop() 和 heappush()
，这个函数的效率更高。
>>> heapreplace(heap, 0.5)
0
>>> heap
[0.5, 1, 5, 3, 2, 7, 9, 8, 4, 6]
>>> heapreplace(heap, 10)
0.5
>>> heap
[1, 2, 5, 3, 6, 7, 9, 8, 4, 10]
10.3.2. 双端队列¶
在需要按添加元素的顺序进行删除时，双端队列很有用。在模块collections中，包含类型deque以及其他几个集合（collection）类型。 与集合（set）一样，双端队列也是从可迭代对象创建的，它包含多个很有用的方法。
>>> from collections import deque
>>> q = deque(range(5))
>>> q.append(5)
>>> q.appendleft(6)
>>> q
deque([6, 0, 1, 2, 3, 4, 5])
>>> q.pop()
5
>>> q.popleft()
6
>>> q.rotate(3)
>>> q
deque([2, 3, 4, 0, 1])
>>> q.rotate(-1)
>>> q
deque([3, 4, 0, 1, 2])