堆
是一个二叉树，它的每个父节点的值都只会小于或等
于所有孩子节点（的值）。
• 它使用了数组来实现：从零开始计数，对于所有的 k ，
都有 heap[k] <= heap[2k+1] 和 heap[k] <= heap[2k+2]。
• 堆最有趣的特性在于最小的元素总是在根结点：heap[0]。
| 函数 | 描述 |
|---|---|
| heapq.heapify(x) | 将list x 转换成堆 |
| heapq.heappush(heap, item | 将 item 的值加入 heap 中，保持堆的不变性。 |
| heapq.heappop(heap) | 弹出并返回 heap 的最小的元素，保持堆的不变性。使用 heap[0] ，可以只访问最小的元素而不弹出它。 |
heapq.heappushpop(heap, item)
• 将 item 放入堆中，然后弹出并返回
heap 的最小元素。
• 堆大小保持不变。
• 先放进去、再弹出来
互动函数：
heapq.heapreplace(heap, item)
• 弹出并返回 heap 中最小的一项，
同时推入新的 item。
• 堆的大小不变。
• 先弹出来一个，再放一个
• 替换再排序
通用函数：
heapq.merge(*iterables)
将多个已排序的输入合并为一个已排序的输出（例如，
合并来自多个日志文件的带时间戳的条目）。 返回已排
序值的 iterator。
heapq.nlargest(n, iterable)
从 iterable 所定义的数据集中返回前 n 个最大元素组成
的列表。
heapq.nsmallest(n, iterable)
从 iterable 所定义的数据集中返回前 n 个最小元素组成
的列表。
练习：
构造一个堆：
• 删除其中最小的值；
• 在其中增加一个值；
import heapq
x=[1,2,3,4,6,7,9,14,15,17,23,36,0]
heapq.heapify(x)
print(x)
heapq.heappop(x)
print(x)
heapq.heappush(x,8)#之前的堆已经改变，这次改变的是上次的结果
print(x)
运行结果：
[0, 2, 1, 4, 6, 3, 9, 14, 15, 17, 23, 36, 7]
[1, 2, 3, 4, 6, 7, 9, 14, 15, 17, 23, 36]
[1, 2, 3, 4, 6, 7, 9, 14, 15, 17, 23, 36, 8]
栈和队列：
队列：
原则：先进先出
应用场景
• 历史记录：最早生成的，最早丢弃
• 数据备份：最先生成的，最先丢弃
• 打印机控制
• CPU分配等
实现：
from collections import deque #需要进行导入
x=deque([9,7,8])
print(x)
x.append(666)
print(x)
x.popleft() #不用加参数，函数定义了从左边进行执行
print(x)
输出结果：
deque([9, 7, 8])
deque([9, 7, 8, 666])
deque([7, 8, 666])
栈：
原则：后进先出
应用场景：
• 操作回退：Ctrl+Z
• 数据库系统等场景
• 浏览器回退上一页
• 括号匹配
实现：
x=[9,7,8]
print(x)
x.append(666)
print(x)
x.pop()
print(x)
运行结果：
[9, 7, 8]
[9, 7, 8, 666]
[9, 7, 8]
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/61419.html
