import heapq # 这是一个模块，不是类，不需要创建实例，heapq.方法(参数)这种调用方式不是必须的；也可以from heapq import 需要用的方法，然后直接方法(参数)，这种调用方式也可以
""" 
heapq: 这个命名说明了该数据结构的双重特性：
1.Heap(堆): 底层是完全二叉树，满足堆性质(父节点 <= 孩子节点)    
2. Queue(队列): 对外表现为优先队列的接口 -- 每次取出优先级最高(最小)的元素

注: heapq默认实现的是最小堆(堆顶元素最小, 父节点小于等于孩子节点)
"""

# 创建空堆
heap = []
# heapq.heappush(heap, item): 向堆中添加元素
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, -7)
heapq.heappush(heap,0)
print(heap) # [-7, 0, 3, 4]

# heapq.heappop(heap): 弹出并返回最小元素
print(heapq.heappop(heap)) # -7
print(heapq.heappop(heap)) # 0
print(heap) # [3, 4]

# heapq.heapify(list): 将列表原地转换成堆
lst = [4, 6, 1, 3]
heapq.heapify(lst)
print(lst) # [1, 3, 4, 6]

# 利用heapq模块实现最大堆: 存储负值
max_heap = []
# 假设所有的数据是: 2 10 1 -8 要找到最大值
heapq.heappush(max_heap, -2)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap,-1)
heapq.heappush(max_heap, 8)
print(max_heap) # [-10, -2, -1, 8]
print(heapq.heappop(max_heap)) # -10


# 进阶用法: 带优先级的任务队列
tasks = []
# 元组比较: 先比第一个元素, 再比第二个
heapq.heappush(tasks, (2, "write code")) # 第二个参数item要统一用元组或者列表
heapq.heappush(tasks, (1, "fix bug")) # 优先级 1 最高 (因为默认实现的是最小堆, 所以比较也是用的最小性质)
heapq.heappush(tasks, (3, "write tests"))
priority, task = heapq.heappop(tasks)
print(priority, "-----",  task) # 1 ----- fix bug



# heapq.nsmallest(n, iterable): 返回n个最小元素(升序排)
# heapq.nlargest(n, iterable): 返回n个最大元素(降序排)
heap1 = [2, 4, -5, 3, 1]
heapq.heapify(heap1)
print(heap1, "\t", type(heap1)) # [-5, 1, 2, 3, 4] 	 <class 'list'>
print("最小的3个元素: ", heapq.nsmallest(3, heap1)) # 最小的3的元素:  [-5, 1, 2]
print("最大的3个元素: ", heapq.nlargest(3, heap1)) # 最大的3个元素:  [4, 3, 2]

# heapq.merge(*iterables): 用于合并已排序可迭代对象, 返回一个惰性迭代器, 按顺序产生元素
a = [1, 3, 5]
b = [2, 6, 4, 8]
merged = heapq.merge(a, b)
print(merged) # <generator object merge at 0x000002247BFECEB0>
print(list(merged)) # [1, 2, 3, 5, 6, 4, 8] 这里输出的不是完全有序的，是因为b不是有序的； 每个输入必须本身先有序heapq.merge()返回的才是有序的(只做多路归并不做内部排序)

c = [7, 8, 10]
print(tuple(heapq.merge(b, c))) # (2, 6, 4, 7, 8, 8, 10)

from heapq import heappush, heappop
heap = []
heappush(heap, (10,20))
heappush(heap, (10, -7))
heappush(heap, (10, -77))
print(heap) # [(10, -77), (10, 20), (10, -7)]

这里可以看出，用heapq实现优先级队列并不是整体有序的，我们想要的结果是如果第一个元素相同，则比较第二个元素，然后从小到大输出

heapq实现的是二叉最小堆，

它只保证：

• 父节点 <= 子节点（堆的性质）
• 不保证兄弟节点之间的顺序

可以用：

res = []
while heap:
    res.append(heapq.heappop(heap)) # res存储的就是我们想要的结果

或者用sorted()函数对可迭代对象进行排序并指定key参数，.sort()只能用在列表上