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

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

(最小)堆是满足下面条件的二叉树:

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

堆根节点是最小的节点,堆的深度永远是$\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,效率自然更快
欧尼酱,人家想喝可乐!