堆（heap ）是一种经典的数据结构，C++ STL 中优先队列 priority_queue 和 Python 中的 heapq 都是堆的一种实现。这里说明一下堆的原理和 heapq 的使用：

在我的这篇博客 中搜索 优先队列 可以看到堆的简单介绍。

（最小）堆是满足下面条件的二叉树

  • 父节点小于等于子节点
  • 用列表或者数组保存（这个也不是必须的，但一般都是这样做的）

堆根节点是最小的节点，堆的深度永远是 $O(\log n)$, 即是平衡的

支持的操作

  • 插入一个元素： 将它放在最后面，向上更新 $O(\log n)$
  • 删除最小的元素： 将最后的元素放在根节点，向下更新 $O(\log n)$
  • 查看最小的元素（根节点）
  • 将一个列表初始化： 将列表从根更新，然后依次递归更新 $O(n)$

从上述操作可知，堆可以用于 堆排序，整体复杂度 $O(n \log n)$

实现一个堆还是挺简单的，不过我们没必要再造轮子了。 下面用例子看一下 Python 堆的使用

1
2
3
4
5
6
7
8
9
10
11
import random
import heapq
# from heapq import *
x= list(range(10))
random.shuffle(x)
heapq.heapify(x)
print(x)
heapq.heappop()
heapq.heappush(x,3)
heapq.heapreplace(x,-1)
heapq.heappushpop(x,-2) #先push后pop，效率自然更快