堆(heap)
- Python没有独立的堆类型,而只有一个包含一些堆操作函数的模块,只有小顶堆,没有大顶堆。
- 这个模块名为heapq(其中的q表示队列),它包含6个函数,其中前4个与堆操作直接相关。
- 必须使用列表来表示堆对象本身。
常用函数
函 数 描 述
heappush(heap, x) 将x压入堆中
heappop(heap) 从堆中弹出最小的元素
heapify(heap) 让列表具备堆特征
heapreplace(heap, x) 弹出最小的元素,并将x压入堆中
nlargest(n, iter) 返回iter中n个最大的元素
nsmallest(n, iter) 返回iter中n个最小的元素
堆特征(heap property)
- 位置i处的元素总是大于位置i // 2处的元素(反过来说就是小于位置2 * i和2 * i + 1处的元素)。
- 这是底层堆算法的基础,称为堆特征(heap property)
例子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| import heapq from random import shuffle
heap = list(range(10)) shuffle(heap)
heapq.heapify(heap) print(type(heap)) print(heap)
heapq.heappush(heap, 11) print(heap)
item = heapq.heappop(heap) print(item) print(heap)
items = heapq.nlargest(3, heap) print(items) print(heap)
|
在python中使用大顶堆
- 将push(e)改为push(-e)、pop(e)改为-pop(e)
- 其他参考小顶堆