Python小根堆

# heapq是Python标准库，提供了构建小根堆和大根堆的基本方法

from heapq import heappush, heappop


array = [10, 6, 8, 2, 1, 3] # 初始的无序列表
h = [] # 空列表，待会用于存小根堆
for num in array:
    heappush(h, num) # 将数num放入堆中，heappush方法保证放入之后h是小根堆

print(array) # [10, 6, 8, 2, 1, 3]
print(h) # [1, 2, 3, 10, 6, 8] 堆顶元素总是最小

t = heappop(h) # 弹出并返回h中最小的元素，即堆顶元素，同时返回之后又保证了堆的不变性
print(t) # 1
print(h) # [2, 6, 3, 10, 8]

堆优化版本的dijkstra

"""
堆优化版本的Dijkstra算法：用来处理稀疏图问题(点数和边数差不多的情况，稠密图边数大概是点数的平方倍)
先想一下朴素做法：dijkstra是解决单元最短路问题，适用场景是不存在负权边
1.首先初始化所有点到起点的距离为正无穷float("inf")，起点到起点的距离为0
2.总共n个循环，每个循环需要找到不在最短集合中且到起点距离最小的点，把这个点加入到集合当中
3.用刚才找到的点更新所有点到起点的距离

想一想如何优化：
因为每次需要找到到起点距离最小的点，考虑使用小根堆优化，对应Python的heapq
同时因为是稀疏图，就需要用defaultdict来存图
因为输入的时候不处理重边，在堆中可能有冗余，判断一下就行
O(mlogn)

-----------------------------------------------------------
邻接表的模板
from collections import defaultdict

graph = defaultdict(list)

for i in range(n):
    x, y, c = map(int, input().split())
    graph[x].append([y, c])
"""
from collections import defaultdict
from heapq import heappush, heappop


def dijkstra():
    dist[1] = 0 # 初始化起点到起点的距离为0
    h = [] # 初始化小根堆
    heappush(h, [0, 1]) # 将起点加到堆中

    while h:
        _, i = heappop(h)

        # 如果这个点已经在集合当中了，就不会再更新
        if st[i]:
            continue
        st[i] = True # 否则就找到距离最下的点

        # 更新i这个点所有出去的点到起点的距离
        for item in graph[i]:
            j, distance = item
            if dist[j] > dist[i] + distance:
                dist[j] = dist[i] + distance
                heappush(h, [dist[j], j])

    if dist[n] == float("inf"):
        return -1
    return dist[n]



n, m = map(int, input().strip().split())

graph = defaultdict(list) # 邻接表
for i in range(m):
    a, b, c = map(int, input().strip().split())
    graph[a].append([b, c])

# print(graph)
dist = [float("inf") for _ in range(1+n)] # 初始化所有点到起点的距离为无穷大
st = [False for _ in range(n+1)] # 判断每个点是不是已经在集合当中了


print(dijkstra())