python内置堆如何实现

1.简介

堆，又称优先队列，是一个完全二叉树，它的每个父节点的值都只会小于或等于所有孩子节点（的值）。 它使用了数组来实现：从零开始计数，对于所有的 k ，都有 heap[k] <= heap[2k+1] 和 heap[k] <= heap[2k+2]。 为了便于比较，不存在的元素被认为是无限大。 堆最有趣的特性在于最小的元素总是在根结点：heap[0]。

python的堆一般都是最小堆，与很多教材上的内容有所不同，教材上大多以最大堆，由于堆的表示方法，从上到下，从左到右存储，与列表十分相似，因此创建一个堆，可以使用list来初始化为 [] ，或者你可以通过一个函数 heapify() ，来把一个list转换成堆。如下是python中关于堆的相关操作，从这可以看出，python确实是将堆看作是列表去处理的。

2.堆的相关操作

heapq.heappush(heap, item)

将 item 的值加入 heap 中，保持堆的不变性。会自动依据python中的最小堆特性，交换相关元素使得堆的根节点元素始终不大于子节点元素。

原有数据是堆

1b5e3ea7e8521d4c720c1b54bd636d73

上述操作流程如下：

1.当进行第一次push(5, ‘write code’)时

2.当进行第二次push(7, ‘release product’)时，符合堆的要求

3.当进行第三次push(1, ‘write spec’)时，

4.依据python的堆的最小堆特性，5>1 ，交换5和1

5.当进行最后依次push(3, ‘create tests’)时

6.依据python堆的最小堆特性，7>3，交换7与3

7.符合要求，因此结果为[(1, ‘write spec’), (3, ‘create tests’), (5, ‘write code’), (7, ‘release product’)],弹出元素则是堆顶元素，数字越小，优先级越大。

以上是python内置堆如何实现的详细内容。更多信息请关注PHP中文网其他相关文章！