When I was doing competitive programming and tried to implement Dijkstra in Python, I wanted heapq to be sorted by distance by inserting something like ("vertex name", distance), but I was a little worried about the behavior at that time. It is a memo article that I just confirmed.
I wondered if something like a custom operator could be put in, but it usually slows down if I make it myself, so I wanted to avoid it as much as possible.
I think it's a heapq specification or a Python comparison operator specification, but I'll summarize it because it's a big deal.
If you plunge the list into heapq, ** Ascending order of the first element → Ascending order of the second element **. It seems that the evaluation of each element is done independently, so it is okay to mix numbers and character strings.
In short
[[1,4],[2,0],[0,1],[0,3]]
↓
[[0,1],[0,3],[1,4],[2,0]]
It will be like.
import heapq
import random
a = []
heapq.heapify(a)
for i in range(5):
heapq.heappush(a,[random.randint(0,10) for i in range(2)])
while a:
print(heapq.heappop(a))
[0, 10]
[2, 7]
[2, 7]
[2, 10]
[5, 0]
for i in range(5):
heapq.heappush(a,[random.randint(0,10),chr(random.randint(97,97+26))])
while a:
print(heapq.heappop(a))
[0, 'k']
[4, 'd']
[4, 'l']
[5, 'c']
[7, 'o']
that's all. I like Python because it makes me feel good, but I don't like it because I sometimes get into an accident (contradiction).
Recommended Posts