1. 模块：heapq

1.1 模块方法汇总

__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
           'nlargest', 'nsmallest', 'heappushpop']

"""
heappush: Push item onto heap, maintaining the heap invariant.
heappop: Pop the smallest item off the heap, maintaining the heap invariant.
heapify: ransform list into a heap, in-place, in O(len(x)) time.
heapreplace: Pop and return the current smallest value, and add the new item.
merge: Merge multiple sorted inputs into a single sorted output.
nlargest: Find the n smallest elements in a dataset. Equivalent to:  sorted(iterable, key=key)[:n]
nsmallest: Find the n largest elements in a dataset. Equivalent to:  sorted(iterable, key=key, reverse=True)[:n].
heappushpop: Fast version of a heappush followed by a heappop.
"""

1.2 方法详解和实践

refer: Python标准库模块之heapq
refer: 创建堆

1.2.1 创建堆 heapify

概念：
创建堆指的是初始化一个堆实例。在创建堆的过程中，我们也可以同时进行堆化操作。堆化就是将一组数据变成堆的过程。
创建方法：
- 使用一个空列表，然后使用heapq.heappush()函数把值加入堆中；
- 或者使用heap.heapify(list)转换列表成为堆结构
  时间复杂度： O(N)
  空间复杂度： O(N)

语法：heapify(list)

import heapq
seqs = [5, 2, 4, 7, 11, 3, 12, 65, 34]
heap = []
for v in seqs:
    heapq.heappush(heap, v)
print(heap)     # [2, 5, 3, 7, 11, 4, 12, 65, 34]

heapq.heapify(seqs)
print(seqs)     # [2, 5, 3, 7, 11, 4, 12, 65, 34]

print([heapq.heappop(seqs) for _ in range(len(seqs))])   # out：[2, 3, 4, 5, 7, 11, 12, 34, 65]

import heapq
# 创建一个空的最小堆
minHeap = []
heapq.heapify(minHeap)

# 创建一个空的最大堆
# 由于Python中并没有内置的函数可以直接创建最大堆，所以一般我们不会直接创建一个空的最大堆。

# 创建带初始值的「堆」， 或者称为「堆化」操作，此时的「堆」为「最小堆」
heapWithValues = [3,1,2]
heapq.heapify(heapWithValues)

# 创建最大堆技巧
# Python中并没有内置的函数可以直接创建最大堆。
# 但我们可以将[每个元素*-1]，再将新元素集进行「堆化」操作。此时，堆顶元素是新的元素集的最小值，也可以转换成原始元素集的最大值。
# 示例
maxHeap = [1,2,3]
maxHeap = [-x for x in maxHeap]
heapq.heapify(maxHeap)
# 此时的maxHeap的堆顶元素是-3
# 将-3转换为原来的元素3，既可获得原来的maxHeap中最大的值是3

1.2.2 插入元素 heappush

语法：heappush(heap, item)

# 最小堆插入元素
heapq.heappush(minHeap, 1)
# 最大堆插入元素
# 元素乘以-1的原因是我们将最小堆转换为最大堆。
heapq.heappush(maxHeap, 1*-1)

1.2.3 获取元素

堆获取元素通常指获取堆顶元素

语法：heap[0]

# 最小堆获取堆顶元素，即最小值
minHeap[0]
# 最大堆获取堆顶元素，即最大值
# 元素乘以 -1 的原因是：我们之前插入元素时，将元素乘以 -1，所以在获取元素时，我们需要乘以 -1还原元素。
maxHeap[0]*-1

1.2.4 删除堆顶元素 heapq.heappop

语法：heapq.heappop(heap)

# 最小堆删除堆顶元素
heapq.heappop(seqs)
# 最大堆删除堆顶元素
heapq.heappop(seqs)

1.2.5 替换堆顶元素 heapq.heaprepalce

语法： heapq.heapify(heap, item)

import heapq

seqs = [5, 2, 4, 7, 11, 3, 12, 65, 34]
heapq.heapify(seqs)
print(seqs)     # [2, 5, 3, 7, 11, 4, 12, 65, 34]
heapq.heapreplace(seqs, 200)    
print(seqs)     # [3, 5, 4, 7, 11, 200, 12, 65, 34]