python使用堆/优先队列

想用python实现一下单源最短路的Dijkstra算法，却发现不会使用python的优先队列，于是学习了一下。

学习的博客：https://www.yangyanxing.com/article/priorityqueue_in_python.html

https://blog.csdn.net/liu2012huan/article/details/53264162

博主想简要小结一下，先说明，博主并没有深刻了解python堆/队列的实现，没有认真读过官方文档，没看过源码什么的。只是博主照着上面两篇博文照葫芦画瓢，给一个最简单的使用方式而已。

 1 from queue import Queue,PriorityQueue
 2 
 3 # 使用heapq实现优先队列
 4 #定义一个可比较对象
 5 class pqueue:
 6     def __init__(self,x,y):
 7         self.x = x
 8         self.y = y
 9 
10     def __lt__(self, other):        #定义了<，像C++的重载<运算符
11         return self.x<other.x
12 
13 
14 def main():
15     pq = PriorityQueue()
16     while 1:
17         opt=int(input())
18         if opt==0:      #输入0，结束测试
19             break
20         if opt==1:      #输入1，输入数字对
21             x,y=map(int,input().split())
22             pq.put(pqueue(x,y))    #插入数据
23         if opt==2:      #输入2，输出优先队列队头
24             tmp=pq.get()
25             print(tmp.x,tmp.y)    #提取队头
26 
27 
28 if __name__=="__main__":
29     main()

然后是用法示例，用python实现Dijkstra算法：

 1 from queue import Queue,PriorityQueue
 2 
 3 class pair:
 4     def __init__(self,x,y):
 5         self.x = x
 6         self.y = y
 7 
 8     def __lt__(self, other):     
 9         return self.y<other.y
10 
11 class edge:
12     def __init__(self,x,y,z):
13         self.x = x
14         self.y = y
15         self.z = z
16 
17 
18 def Dijkstra(n,s,edges):
19     pq = PriorityQueue()
20     vis=[0]*(n+1)
21     dis=[0x3f3f3f3f]*(n+1)
22     dis[s]=0
23     pq.put(pair(s,0))
24     while not pq.empty():
25         now=pq.get()
26         if vis[now.x]==1:
27             continue
28         vis[now.x]=1
29         for e in edges[now.x]:
30             if dis[now.x]+e.z<dis[e.y]:
31                 dis[e.y]=dis[now.x]+e.z
32                 pq.put(pair(e.y,dis[e.y]))
33     INF=(1<<31)-1
34     for i in range(1,n+1):
35         print(dis[i] if dis[i]!=0x3f3f3f3f else INF,end=' ')
36 
37 def main():
38     n,m,s=map(int,input().split())
39     edges=[]
40     for _ in range(n+1):
41         edges.append([])
42     for _ in range(m):
43         x,y,z=map(int,input().split())
44         edges[x].append(edge(x,y,z))
45     Dijkstra(n,s,edges)
46 
47 
48 if __name__=="__main__":
49     main()