堆
Heap是一种数据结构，堆的实现是通过二叉堆，也是一种二叉树。二叉树Binary Tree是每个节点最多有两个子树的数结构，分为左子树和右子树。
术语
image.png
- 树根F：最顶端的称之为
树根 - 节点：每个字母所在的位置称之为
节点，每个节点向下分散出来两个节点。并不是所有的节点都有两个子节点 - 完全二叉树：不是所有的节点都有两个子节点的二叉树
- 满二叉树：所有的节点都有两个子节点的二叉树
通过二叉树实现的对象的特点：
- 节点的值大于等于（或者小于等于）任何子节点的值
- 节点左子树和右子树是一个二叉树。如果父节点的值总是大于或者等于任何一个子节点的值，称之为最大堆；反之称之为最小堆。
heapq模块
heapq中的heap 就是堆，q就是queue队列的意思。
import heapq # 导入模块
heapq.__all__ # 查看模块的所有方法
# 结果
['heappush', # 向堆中添加元素
'heappop', # 删除元素
'heapify', # 将列表等直接变成堆
'heapreplace', # 替换堆中的某个元素，理解成直接先删除再插入进去
'merge',
'nlargest',
'nsmallest',
'heappushpop']
heappush(heap, x)
向堆中添加元素x
Help on built-in function heappush in module _heapq:
heappush(...) # 将元素item添加到heap中，里面的元素不仅可以是数字，也可以是字符串等
heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant.
heap = [] # 定义空列表用于存放元素
heapq.heappush(heap,3) # 添加多个元素，添加以后的位置是随机的，自动按照二叉树的结构进行存储
heapq.heappush(heap,8)
...
heapq.heappush(heap,0)
heap
[0, 1, 2, 4, 7, 3, 10, 8]
heappop(heap)
删除堆中的最小值，并且返回该值，再重新按照完全二叉树进行排列。
image.png
heapify
如果已经建立了一个列表，利用heapify()可以将列表直接转换成堆。
image.png
heapreplace()
替换操作，相当于是先删除再进行添加，heapreplace = heappop + heappush
经过下面的三次尝试发现：
每次替换的都是第一个元素
deque双端队列
引子：lst = [1,3,5]怎么向最左边追加元素呢？列表的方法中append是最右边追加元素。
- extend：将两个列表进行合并
-
append：最右边追加元素
image.png
通过deque来解决：
from collections import deque
list3 = [1,9,4,6,8]
deque_list3 = deque(list3) # 先转成deque对象
deque_list3.append(7) # 右边增加
deque_list3
# 结果
deque([1, 9, 4, 6, 8, 7])
deque_list3.appendleft(5) # 左边增加
deque_list3
# 结果
deque([5, 1, 9, 4, 6, 8, 7])
# 关于删除操作
deque_list3.pop() # 删除最右边的元素
print(deque_list3)
deque_list3.popleft() # 删除最左边的元素
print(deque_list3)
# 结果
deque([5, 1, 9, 4, 6, 8])
deque([1, 9, 4, 6, 8])
image.png
deque_list3.extend([4,9,3])
deque_list3
image.png
- 关于rotate()方法
该方法rotate(n)的功能是将序列旋转n次。n是正数：表示序列中的元素是按照顺时针排序的。顺时针！顺时针！顺时针！。n是负数表示逆时针
image.png
图片发自简书App
- 关于merge方法
list(heapq.merge(sorted([1,9,4,2]), sorted([6,7,0,5]), sorted([10,18,28]))) # 里面的元素必须先排好序
image.png
