「 This is my participation 2022 For the first time, the third challenge is 15 God , Check out the activity details ：2022 For the first time, it's a challenge 」.
The school committee said that we should roll up the built-in queue , As shown earlier, there is a simple first in and last out , First in first out queue .
Today, the priority queue is shown first .
This is a queue that knows how to distinguish priorities . Before FIFO/FILO These are put in order , Put it in first or leave first , Or get out of the line later .
The actual application scenario is similar to our daily , For example, we go to a fancy restaurant for dinner .
Usually they set membership levels , For example, regular customers VIP, Or that kind of advanced VIP（VVIP）, These join the team .
The front desk staff will arrange customers to enter the site according to customer registration .
At this time, priority queues come in handy .
The priority queue can be put into the element format as follows ：
q = PriorityQueue()
# Binary （ Priority series , data ）
q.put((3, ' The small white '))
Copy code The following is the simulation of the whole queue ：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2022/2/14 11:13 Afternoon
# @Author : LeiXueWei
# @CSDN/Juejin/Wechat: Lei Xuewei
# @XueWeiTag: CodingDemo
# @File : priorityqdemo.py
# @Project : hello
from queue import PriorityQueue
q = PriorityQueue()
q.put((3, ' The small white '))
# After the
q.put((2, ' Lei Xuewei '))
# The last to
q.put((1, ' floret '))
while not q.empty():
next_item = q.get()
print(" welcome %s Have meals :" % str(next_item))
Copy code First , Xiaobai didn't VIP Get the number first . Then the school committee , Xiaohua goes to the restaurant to line up one after another .
Run the code directly , You can see that Xiaohua finally arrived , But she lacks the first one to go into the dining room .
Can't , She is VVIP, Highest level （ The value of the third element is the smallest ） So put it in the front .
The renderings are as follows ：
So it's very ‘ reasonable ’（ Can't , Who told you to line up at a fancy restaurant , Go to an ordinary restaurant , Let's use ordinary FIFO Queue to manage the dining order ）.
open queue This library directly sees PriorityQueue Source code of this class ：
Too simple. , Directly inherited Queue Parent class .
However, we see that the priority queue covers _put Method , It was used heappush Method to put elements into binary heap （ This is in heapq A method in the built-in Library , There is also the implementation of taking elements ）.
def heappush(heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
_siftdown(heap, 0, len(heap)-1)
Copy code headpush The new team elements are directly put at the end of the team （ front heap=[])
Then perform the following method to place the elements ：
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if newitem < parent:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
Copy code Use here [ The smallest binary pile (baike.baidu.com/item/%E6%9C…) , By constantly comparing with the parent node （ The location of the parent node is parentpos = (pos - 1) >> 1）.
Round robin , If the new element is smaller than the parent node , The current newly added node moves up （ That is, the parent node moves down to the new position each time the new node is placed ）
Until you find a position where the parent node is less than the value of the new node , Stop moving , The operation of joining the team is completed .
This paragraph is brain burning , First explain this join the team . Then make a graphic display .
Priority queue , It's like waiting in a high-end restaurant or bank VIP/VVIP such , Special arrangements for special groups .
The internal implementation uses the data structure of binary tree , Later, the school committee will make a picture display .
The previous academic committee said this , Put them together again , Comparison Review ：
LIFO queue , It's like a supermarket container , Items in the back , First seen by consumers .
First in first out queue , It's like waiting in line for a medical examination , It's like waiting in line for dinner . It must be first come, first arranged .
Priority queue , It's like waiting in a high-end restaurant or bank VIP/VVIP such , Special arrangements for special groups .
like Python Friend, , Please pay attention to Python Basic column or Python From getting started to mastering the big column
Continuous learning and continuous development , I'm Lei Xuewei ！
Programming is fun , The key is to understand the technology thoroughly .
Welcome to wechat , Like support collection !
