Behavior when listing in Python heapq

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.

Conclusion

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.

Verification 1


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]

Verification 2


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

Behavior when listing in Python heapq
Behavior when saving python datetime object in MongoDB
Attention when os.mkdir in Python
Precautions when using pit in Python
Check the behavior when assigning Python
When using regular expressions in Python
When writing a program in Python
Behavior when returning in the with block
Create ScriptableObject in Python when building ADX2
Precautions when pickling a function in python
[python, multiprocessing] Behavior for exceptions when using multiprocessing
When looking at memory usage in Python 3
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
SendKeys in Python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
[Tips] Easy-to-read writing when connecting functions in Python
When codec can't decode byte appears in python
When I try matplotlib in Python, it says'cairo.Context'
[python, CPython] GC behavior when throwing an exception
Precautions when dealing with control structures in Python 2.6
Note on encoding when LANG = C in Python
Character encoding when dealing with files in Python 3
Behavior when Trainable = False of Container in Keras
I tried non-blocking I / O Eventlet behavior in Python