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
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
・ 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.
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
Click here for more detailed explanation https://docs.python.org/ja/3/library/heapq.html
Recommended Posts