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
- See here for the detailed algorithm.
Heap condition: Each node is less than or equal to its child nodes Initial sequence: [1, 6, 8, 0, -1]
Recommended Posts