Python中heapq模块被称为堆队列算法，也成为优先队列算法。堆的主要用途是优先队列和堆排序。

堆（二叉树的应用）：最小堆，最大堆。

• 最小堆：父节点小于等于所有子节点，左右子节点无大小要求（但先有左节点才有右节点）。
• 最大堆：父节点大于等于所有子节点，左右子节点无大小要求（但先有左节点才有右节点）。

通常用数组实现堆：

• 最小堆：堆[i] <= 堆[2i + 1] and 堆[i] <= 堆[2i + 2]，i从0开始。即父节点小于等于左右子节点。
• 最大堆：堆[i] >= 堆[2i + 1] and 堆[i] >= 堆[2i + 2]，i从0开始。即父节点大于等于左右子节点。

heapq模块操作最小堆，添加元素时按最小堆排序，取出元素时则取出堆中最小值。（但最大堆的效果可用符号负号“-”实现。见本文末尾）

---

导入模块：

import heapq

---

最小堆实现： 

1、创建最小堆

（1-1）python中可使用空列表： [ ]

# 创建堆
h = []

（1-2）可使用函数将已有列表转为堆：heapq.heapify(...)

# 创建堆（将已有列表转为堆）
heapq.heapify(已有列表)

2、往最小堆中添加元素：heapq.heappush(...)

# 往最小堆中添加元素
heapq.heappush(最小堆, 元素)

3、从最小堆中取出最小值：heapq.heappop(...)

# 从最小堆中取出最小值
heapq.heappop(最小堆)

注：若堆中没有元素，则报错IndexError。 

4、添加元素和取出最小值同时操作

（4-1）先heappush再heappop：heapq.heappushpop(...)

# 先heappush再heappop：先将新元素添加到堆，再从堆中取出最小值
heapq.heappushpop(最小堆, 新元素)

注：先将新元素添加到堆，再从堆中取出最小值。若添加的新元素为最小值，则取出的就是新添加的该元素。

（4-2）先heappop再heappush：heapq.heapreplace(...)

# 先heappop再heappush：先从堆中取出最小值，再往堆中添加新元素
heapq.heapreplace(最小堆, 新元素)

注：先从堆中取出最小值，再将新元素添加到堆。若添加的新元素为最小值，则取出的不是新添加的该元素，而是添加前的最小值。

5、从最小堆中获取n个最大值或最小值

（5-1）从最小堆中获取n个最大值：heapq.nlargest(...)

# 从最小堆中获取n个最大值
heapq.nlargest(n, 可迭代对象, key=None)

注：参数key是条件，例如：字符串按小写字母获取最大值，元组按下标为1的值获取最大值，等等。 

（5-2）从最小堆中获取n个最小值：heapq.nsmallest(...)

#从最小堆中获取n个最小值
heapq.nsmallest(n, 可迭代对象, key=None)

注：参数key是条件，例如：字符串按小写字母获取最小值，元组按下标为1的值获取最小值，等等。 

6、将多个可迭代对象拼接成一个迭代器：heapq.merge(...)

# 将多个可迭代对象拼接成一个迭代器（已排序，确保参数中的可迭代对象已排序）
heapq.merge(*iterables, key=None, reverse=False)

注：若迭代器从小到大排序，则需参数中输入的可迭代对象已从小到大排序。若迭代器降序（参数reverse=True）排序，则需可迭代对象已降序排序。

注：参数key是迭代器排序的条件，例如：字符串按小写字母排序，元组按下标为1的值排序，等等。 

---

最大堆实现：

1、往堆中添加元素时，元素前面加负号。即堆中各元素为负数，元素值越大、负数后越小。

2、从堆中取出最小值时，前面加负号。即元素最小的（负数值越小、原值越大），负数后即最大值。