Python札记46_堆Heap

堆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

Python札记46_堆Heap

• 关于merge方法

list(heapq.merge(sorted([1,9,4,2]), sorted([6,7,0,5]), sorted([10,18,28])))   # 里面的元素必须先排好序

image.png