Python基础(标准库)：heapq(堆)

见贤思齐

1.官方文档heapq---堆队列算法—Python3.12.4文档2.相关概念堆heap是一种具体的数据结构（concrete datastructures）；优先级队列priorityqueue是一种抽象的数据结构（abstract datastructures），可以通过堆、二叉搜索树、链表等多种方式来实现priorityqueue，其中，堆是最流行的实现优先级队列的具体数据结构。2.1优先级队列PriorityQueue抽象数据结构是一种逻辑上的概念，描述了数据的组织方式和操作方式。优先级队列PriorityQueue通常用于优化任务执行，其目标是处理具有最高优先级的任务。任务完成后，其优先级降低，并返回到队列中。PriorityQueue支持三种操作:is_empty：检查队列是否为空。add_element：向队列中添加一个元素。pop_element：弹出优先级最高的元素。对于元素的优先级有两种约定（约定或惯例convention，指约定俗称的用法或含义，特定上下文中使用的特定术语、符号、语法或行为的含义）：1.最大的元素具有最高的优先级；2.最小的元素具有最高的优先级。这两种约定其实是等价的，如果元素由数字组成，那么使用负数即可完成转换。Pythonheapq模块使用第二种，这也是两种约定中更常见的一种。在这个约定下，最小的元素具有最高的优先级。优先级队列对于查找某个极端元素是非常有用的，如：找到点击率前三的博客文章、找到从一个点到另一个点的最快方法、根据到站频率预测哪辆公共汽车将首先到达车站等问题。2.2堆heap2.2.1堆属性堆是特殊的完全二叉树（completebinarytree），其中每个上级节点的值都小于等于它的任意子节点（堆属性），堆常用于实现优先级队列。二叉树（binarytree）中，每个节点最多有两个子节点。完全二叉树是一种特殊的二叉树，其定义是:若设二叉树的深度为h，除第h层外，其它各层1~h-1的结点数都达到最大个数，第h层所有的结点都连续集中在最左边。也就是说，完全二叉树的所有非叶子节点都必须被填满，叶子节点都必须连续排列在最左边。满二叉树是特殊的完全二叉树。完全二叉树的性质保证，树的深度是元素数的以2为底的对数向上取整。在堆树中，一个节点的值总是小于它的两个子节点，这被称为堆属性（与二叉搜索树不同，二叉搜索树中，只有左侧节点的值小于其父节点的值）。在堆中，同一层的节点之间并没有大小关系的限制，唯一的限制是每个节点的值必须符合堆属性。add操作：1.创建新节点添加到堆的末尾。如果底层未满，将节点添加到最深层下一个开放槽中，否则，创建一个新的层级，将元素添加到新的层中。2.将新元素与其父节点比较，如果新元素比父节小，则交换它们的位置，直到新元素的值小于其父节点的值或者新元素成为了根节点。pop操作：1.根据堆属性，该元素位于树的根。将堆顶元素弹出，并将堆末尾元素移到堆顶。2.将堆顶元素与其左右子节点比较，将其与较大（或较小）的子节点交换位置，直到堆顶元素的值大于（或小于）其左右子节点的值或者堆顶元素成为了叶子节点。2.2.2性能保证performanceguarantees具体数据结构实现抽象数据结构中定义的操作，并明确性能保证performanceguarantees，即数据规模和操作所需时间之间的关系，性能保证可用于预测程序行为，比如，当输入的大小发生变化时，程序将花费多少时间完成操作。优先级队列的堆实现保证推入（添加）和弹出（删除）元素都是对数时间操作。这意味着执行push和pop所需的时间与元素数量的以2为底的对数成正比。对数增长缓慢。以2为底15的对数约为4，以2为底1万亿的对数约为40。这意味着，如果一个算法在处理15个元素时足够快，那么它在处理1万亿个元素时只会慢10倍。2.2.3堆与二叉搜索树的区别排序方式不同：堆是一种基于完全二叉树的数据结构，它的每个节点都满足堆的性质，即父节点的值大于（最大堆）（或小于，即最小堆）子节点的值。而二叉搜索树则是一种有序的二叉树结构，它的每个节点都满足左子树的节点值小于该节点的值，右子树的节点值大于该节点的值。操作不同：堆常用于实现优先队列，可以快速找到最大或最小值。堆的插入和删除操作都比较快，但查找操作比较慢。而二叉搜索树可以快速查找、插入和删除节点，但是在某些特殊情况下，可能会出现树的不平衡，导致性能下降。强调：Python的heapq模块和堆数据结构一般都不支持查找除最小元素之外的任何元素，如果想检索指定大小的元素，可以使用二叉搜索树。堆作为优先级队列的实现，是解决涉及极端问题的好工具，当在问题描述中存在如：最大、最小、前、底、最低，最优等字眼，表明需要寻找某些极端元素时，可以考虑一下堆。3.PythonheapqModule前面将堆描述为树，不过它是一个完全二叉树，这意味着除了最后一层之外，每层有多少元素是确定的。因此，堆可以使一个列表实现。Python中的heapq模块就是使用列表实现堆的，heapq将列表的第一个元素视为堆的根节点。堆队列中，索引为k的元素与其周围元素之间的关系:它的第一个子结点是2*k+1。它的第二个子结点是2*k+2。它的父结点是(k-1)//2。堆队列中的元素总是有父元素，但有些元素可能没有子元素。如果2*k超出了列表的末尾，则该元素没有任何子元素。如果2*k+1是有效索引，但2*k+2不是，则该元素只有一个子元素。h[k]