Python堆的基本用法

官方链接：https://docs.python.org/3/library/heapq.html

堆，其实是二叉树的一种。Python中的堆其实是小根堆，即每一个父节点都小于等于它的子节点。

堆这种结构在leetcode刷题过程中经常遇到。

对于一个堆heap来说，它最小的元素总是它的根节点，即heap[0]。

对于一个堆来说，它的导入比较简单

import heapq

heap = []
1
2
3

heappush

通过heappush方法可以将数字加入堆中

heapq.heappush(heap,1)

heapq.heappush(heap,2)

heapq.heappush(heap,3)

heap
#[1,2,3]
1
2
3
4
5
6
7
8

heappop

通过heappop的方式，每次返回堆中的最小值。直到heap为空，报错

heapq.heappop(heap)
#1
heapq.heappop(heap)
#2
heapq.heappop(heap)
#3
heapq.heappop(heap)
Traceback (most recent call last):

  File "<ipython-input-41-f09c97e0fb8a>", line 1, in <module>
    heapq.heappop(heap)

IndexError: index out of range
1
2
3
4
5
6
7
8
9
10
11
12
13