堆
应用场景：
- 给定一个无序数组，要求找出前 k 个最大数
- 堆排序
- 查找第K大(小)元素
- 优先队列
- 求动态集合中位数
定义：
堆(heap)，又被为优先队列(priority queue)，即优先级高的先出队。简易理解：堆是一种数学模型，一种排序方式。能满足以上应用场景。
性质：
堆必须符合以下两个条件：
- 是一棵完全二叉树。
- 任意一个节点的值都大于（或小于）左右子节点的值。
若父节点都大于等于左右子节点，则被称为大顶堆，反之，若父节点都小于等于左右子节点则为小顶堆。
内部实现机制：
以小顶堆举例：
上浮（Promotion）
情境: 子节点的键值比父节点的键值小；
动作：交换子节点的键和父节点的键，重复这个过程直到堆的顺序恢复正常
下沉（Demotion）
情境：父节点的键值变得比子节点（一个或者2个） 的键值还大
动作：父节点的键值和比它大的子节点的键值做交换，重复这个操作直到堆的顺序恢复正常
例如：堆排序（Heapsort）内部动作：
python 堆模块heapq：
'''
heap.heapify(list)，
将list转换成为堆，原地，线性时间内。
'''
heap = [8, 7, 3, 4, 5]
heapq.heapify(heap)
print(heap) #[3, 4, 8, 7, 5]
'''
heapq.heappush(heap, item)，
将 item 的值加入 heap 中，保持堆的不变性。
heapq.heappop(heap),
弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出 IndexError 。
使用 heap[0] ，可以只访问最小的元素而不弹出它。
'''
heap = [8, 7, 3, 4, 5]
heapq.heappush(heap, 9) # 加入堆，堆顺序不变
print(heap) #[8, 7, 3, 4, 5, 9]
print(heapq.heappop(heap)) #8，抛出最右边数
print(heap) #[3, 7, 9, 4, 5]
'''
heapq.heappushpop(heap, item)，
将 item 放入堆中，然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。
'''
heap = [1, 2, 3, 4, 5]
print(heapq.heappushpop(heap, 9)) #1，抛出最右边数
print(heap) #[2, 4, 3, 9, 5]
'''
heapq.heapreplace(heap, item)，
弹出并返回 heap 中最小的一项，同时推入新的 item。 堆的大小不变。 如果堆为空则引发 IndexError。
这个单步骤操作比 heappop() 加 heappush() 更高效，并且在使用固定大小的堆时更为适宜。 pop/push 组合总是会从堆中返回一个元素并将其替换为 item。
返回的值可能会比添加的 item 更大。 如果不希望如此，可考虑改用 heappushpop()。 它的 push/pop 组合会返回两个值中较小的一个，将较大的值留在堆中。
'''
nums = [9, 2, 4, 5, 7]
heapq.heapify(nums)
print(heapq.heapreplace(nums, 23)) #2
print(nums) #[4, 5, 23, 9, 7]
'''
heapq.merge(*iterables, key=None, reverse=False)，
将多个已排序的输入合并为一个已排序的输出（例如，合并来自多个日志文件的带时间戳的条目）。 返回已排序值的 iterator。
类似于 sorted(itertools.chain(*iterables)) 但返回一个可迭代对象，不会一次性地将数据全部放入内存，并假定每个输入流都是已排序的（从小到大）。
具有两个可选参数，它们都必须指定为关键字参数。
key 指定带有单个参数的 key function，用于从每个输入元素中提取比较键。 默认值为 None (直接比较元素)。
reverse 为一个布尔值。 如果设为 True，则输入元素将按比较结果逆序进行合并。 要达成与 sorted(itertools.chain(*iterables), reverse=True) 类似的行为，所有可迭代对象必须是已从大到小排序的。
在 3.5 版更改: 添加了可选的 key 和 reverse 形参。
'''
import heapq
num1 = [32, 3, 5, 34, 54, 23, 132]
num2 = [23, 2, 12, 656, 324, 23, 54]
num1 = sorted(num1)
num2 = sorted(num2)
res = heapq.merge(num1, num2)
print(list(res))
#[2, 3, 5, 12, 23, 23, 23, 32, 34, 54, 54, 132, 324, 656]
import itertools
num1 = [32, 3, 5, 34, 54, 23, 132]
num2 = [23, 2, 12, 656, 324, 23, 54]
res1 = sorted(itertools.chain(num1, num2))
print(res1)
#[2, 3, 5, 12, 23, 23, 23, 32, 34, 54, 54, 132, 324, 656]
'''
heapq.nlargest(n, iterable, key=None)，
从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。
如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key, reverse=True)[:n]。
heapq.nsmallest(n, iterable, key=None)，
从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。
如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key)[:n]。
后两个函数在 n 值较小时性能最好。 对于更大的值，使用 sorted() 函数会更有效率。 此外，当 n==1 时，使用内置的 min() 和 max() 函数会更有效率。 如果需要重复使用这些函数，请考虑将可迭代对象转为真正的堆。
'''
list1 = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]
list2 = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
print(heapq.nlargest(3, list1)) #[99, 92, 88]
print(heapq.nsmallest(3, list1)) #[12, 25, 34]
print(heapq.nlargest(2, list2, key=lambda x: x['price']))
#[{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}]
print(heapq.nlargest(2, list2, key=lambda x: x['shares']))
#[{'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'IBM', 'shares': 100, 'price': 91.1}]