堆的基本操作

堆（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）

例子

import heapq
from random import shuffle

heap = list(range(10))
shuffle(heap)

heapq.heapify(heap)
print(type(heap))  # <class 'list'>
print(heap)  # [0, 3, 1, 4, 7, 8, 2, 5, 6, 9]

heapq.heappush(heap, 11)
print(heap)  # [0, 3, 1, 4, 7, 8, 2, 5, 6, 9, 11]

item = heapq.heappop(heap)
print(item)  # 0
print(heap)  # [1, 3, 2, 4, 7, 8, 11, 5, 6, 9]

items = heapq.nlargest(3, heap)
print(items)  # [11, 9, 8]
print(heap)  # [1, 3, 2, 4, 7, 8, 11, 5, 6, 9]

在python中使用大顶堆

• 将push(e)改为push(-e)、pop(e)改为-pop(e)
• 其他参考小顶堆