Python Priority Queuing The mystery of the result of the heapify function that most people wouldn't be interested in

Introduction

I investigated the mysterious part of the behavior of the priority queue in Python.

Mysterious behavior

Here , when I was checking the priority queue in Python, it was possible to realize it with the heapq library. .. In the above link, the following is described as an example of using heapq.

#Source: https://qiita.com/ell/items/fe52a9eb9499b7060ed6
import heapq  #import of heapq library

a = [1, 6, 8, 0, -1]
heapq.heapify(a)  #List to priority queue
print(a)
#output: [-1, 0, 8, 1, 6](Priority queue a)

Why is the output in this sequence ([-1, 0, 8, 1, 6])? A question arose that no one seemed to be interested in (because I expected ascending order).

Reason: Because the elements of the list are sorted by the heap queue algorithm

In Python, it seems that priority queues are represented by a list, According to python document , the heap queue algorithm sorts the contents of the list. thing.

Here The heap explanation site has a detailed explanation of the heap algorithm. , The tree structure can be represented by a list (assuming the list index of the parent node is i, the left node of the child is 2 * i and the right node is 2 * i + 1). The above output was obtained by swapping the elements in the list so that the parent-child relationship was established.

Sort flow by heap queue algorithm

Heap condition: Each node is less than or equal to its child nodes Initial sequence: [1, 6, 8, 0, -1]

heapq.png

Recommended Posts

Python Priority Queuing The mystery of the result of the heapify function that most people wouldn't be interested in
A function that measures the processing time of a method in python
The result of installing python in Anaconda
Get the caller of a function in Python
View the result of geometry processing in Python
Measure the execution result of the program in C ++, Java, Python.
[Memo] The mystery of cumulative assignment statements in Python functions
The result of Java engineers learning machine learning in Python www
Processing of python3 that seems to be usable in paiza
Have the equation graph of the linear function drawn in Python
[Python] Let's reduce the number of elements in the result in set operations
Try transcribing the probability mass function of the binomial distribution in Python
[Python] A program that calculates the number of socks to be paired
I want to batch convert the result of "string" .split () in Python
The eval () function that calculates a string as an expression in python
The result of making the first thing that works with Python (image recognition)
[Python] Note: A self-made function that finds the area of the normal distribution
Check the behavior of destructor in Python
OR the List in Python (zip function)
[Python3] Rewrite the code object of the function
The basics of running NoxPlayer in Python
In search of the fastest FizzBuzz in Python
How to pass the execution result of a shell command in a list in Python
[Python] The movement of the decorator that can be understood this time ② The decorator that receives the argument
A solution to the problem that the Python version in Conda cannot be changed
You will be an engineer in 100 days --Day 29 --Python --Basics of the Python language 5
[Python] Summary of functions that return the index that takes the closest value in the array
You will be an engineer in 100 days --Day 33 --Python --Basics of the Python language 8
You will be an engineer in 100 days --Day 26 --Python --Basics of the Python language 3
I want to create a priority queue that can be updated in Python (2.7)
Set an upper limit on the number of recursive function iterations in Python
How to find the coefficient of the trendline that passes through the vertices in Python
You will be an engineer in 100 days --Day 32 --Python --Basics of the Python language 7
Correspondence of the event that the result of form.is_valid () is always False in Django2 system
You will be an engineer in 100 days --Day 28 --Python --Basics of the Python language 4
[Python] I examined the practice of asynchronous processing that can be executed in parallel with the main thread (multiprocessing, asyncio).