数据结构-小点堆heapq

heapq python内置的堆结构，小点堆（优先队列）

完全二叉树： 必须现有子节点

最小堆：默认每个节点都小于其子节点

适用于动态添加元素和获取最小值

基本语法：

1.创建，将一个list转换成最小堆 ：heqpq.heapify(list)

创建hq

2.向最小堆中添加元素 ：heapq.heappust(list, a)

添加元素

3.弹出最小元素 : heapq.heappop(list)

弹出最小值

4.弹出最小值的同时，补充一个值进堆 ：heapq.heapreplace(list, b)

追加弹出

5.从可迭代对象中快速获取最大（小）的 N 个元素，效率高于先排序再切片的方式：heapq.nlargest() heapq.nsmallest()

按排序取出前N个值

6.只访问最小值，不改变堆内容： 访问下标[0]

heapq 按最大堆使用， 对每个权重取负值即可

最大堆

heap: 插值和弹出的规则

插值： 将插入的值放在最末尾， 然后依次与其父节点比较，如果小于，则交换位置

插入节点2，节点2，与其父节点5比较，小于，则交换位置

交换后，节点2继续与其子节点1比较，大于，则不交换位置，位置调整结束

弹出： 弹出最小节点，并将最后一个节点放入最小节点的位置，然后依次与其子节点比较，与较小的那个交换位置，直到所有节点满足笑点堆完全二叉树的规则

准备弹出节点1

第一个节点（最小节点）节点1弹出，将最后一个节点：节点5补充到1的位置，然后节点5与其左右子节点比较，由于最小的是节点2，则准备将节点2与5交换

交换2与5后 重新满足小点堆的规则

继续弹出，则按如上步骤：

弹出节点2，节点8补充到最前面，然后依次与其左右子节点比较，与最小的交换位置，调整好树结构

示例：

对事物按优先级排序

其它： 队列中的优先队列

queue PriorityQueue