Review the basics in 1 minute! Python Priority queue for fast minimums

Overview

Python has a convenient queue called heapq, which is used when you want to quickly retrieve the minimum value from a list, so let's review it quickly. Frequent content even in AtCoder

For those in a hurry

All of this article. Third line q = heapq.heapify(a) Be careful because it does not move

a = [1,2,3,4,6,7,8]
#Heapify list with heapify.
heapq.heapify(a)

#Add 5 with heappush.
heapq.heappush(a,5)

#The elements in the heap are extracted by heapop in ascending order.
while a:
  print(heapq.heappop(a))
    
######Execution result######
1
2
3
4
5
6
7
8

Simple explanation

・ Heap **. Heapify (list) ** If you give a list, it will be heaped

・ Heap. ** heap push (heap, element) ** Add a new element to heap (heap version of append in list)

・ Heap. ** heapop (heap) ** Get the smallest value in the heap. The retrieved element is deleted from the heap.

application

I want to create a priority queue that retrieves the maximum value

** All values ​​can be signed in reverse. ** **

a = [1,2,3,4,6,7,8]

#Reverse the sign of the element
for i in range(len(a)):
  a[i] = a[i]*(-1)
heapq.heapify(a)

while a:
  #I will return the sign of the output
  print(heapq.heappop(a)*(-1))

######Execution result######

8
7
6
4
3
2
1

Referenced site

Click here for more detailed explanation https://docs.python.org/ja/3/library/heapq.html

Recommended Posts

Review the basics in 1 minute! Python Priority queue for fast minimums
[Understand in the shortest time] Python basics for data analysis
MongoDB for the first time in Python
Queue processing in Python
Is the priority queue heapq in Competitive Pro (Python)? queue.PriorityQueue? Which one should I use?
Check the operation of Python for .NET in each environment
Try sorting your own objects with priority queue in Python
The story that `while queue` did not work in python
What beginners learned from the basics of variables in python
Google search for the last line of the file in Python
Download the file in Python
Find the difference in Python
Search for strings in Python
Techniques for sorting in Python
Stack and Queue in Python
Implement fast RPC in Python
About "for _ in range ():" in python
Get the Ticker Symbol for US exchange listed stocks in Python
Automatically resize screenshots for the App Store for each screen in Python
[Introduction to Python] How to use the in operator in a for statement?
Dockerfile with the necessary libraries for natural language processing in python
Try using FireBase Cloud Firestore in Python for the time being
[Python] When the priority is the same in Priority Queue, it can be acquired in the order in which it was added to the queue.
Check for memory leaks in Python
Getting the arXiv API in Python
Check for external commands in python
Python in the browser: Brython's recommendation
Save the binary file in Python
Hit the Sesami API in Python
In the python command python points to python3.8
Implement the Singleton pattern in Python
Hit the web API in Python
See python for the first time
Calculate the previous month in Python
Examine the object's class in python
Get the desktop path in Python
What is the python underscore (_) for?
Run unittests in Python (for beginners)
Get the host name in Python
Access the Twitter API in Python
The first step in Python Matplotlib
Implemented in 1 minute! LINE Notify in Python
About the basics list of Python basics
I wrote the stack in Python
Command for the current directory Python
Master the weakref module in Python
Learn the basics of Python ① Beginners
Add syntax highlighting for the Kv language to Spyder in the Python IDE
python> array> Determine the number and initialize> mylist = [idx for idx in range (10)] / mylist = [0 for idx in range (10)] >> mylist = [0] * 10
Switch the module to be loaded for each execution environment in Python
A useful note when using Python for the first time in a while
Get the key for the second layer migration of JSON data in python