“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

In front of the committee said to the built-in queue are masturbated, the front shows a simple fifo, fifO queue.

I showed you the priority queue today.

PriorityQueue

This is a queue that knows how to set priorities. So FIFO and FILO were all in the order that they were put in, and the ones that were put in first either came out first or came out last.

The actual application scenario is similar to our daily life, for example, we go to a fancy restaurant for dinner.

Usually they have a membership level, like a frequent VIP, or a VVIP, and they get in.

The front desk staff will arrange the entry of customers according to their registration.

This is where priority queues come in.

Priority queues can be placed in elements of the following format:

Q = PriorityQueue() # q.put((3, 'white '))Copy the code

Here is a simulation of the entire queue queuing:

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# @time: 2022/2/14 11:13 PM
# @Author : LeiXueWei
# @csDN /Juejin/Wechat: Lei Xuewei
# @XueWeiTag: CodingDemo
# @File : priorityqdemo.py
# @Project : hello

from queue import PriorityQueue

q = PriorityQueue()

q.put((3.'white'))
# after to
q.put((2.'Thunder Committee'))
# the last to
q.put((1.'flower'))

while not q.empty():
    next_item = q.get()
    print("🐰 welcome %s to dinner :" % str(next_item))
Copy the code

First of all, xiaobai didn’t get the number first. Then the committee, floret went to the restaurant in line.

Directly run the code, you can see floret students finally arrived, but she is the first to go into the restaurant hall dinner.

No way, she is VVIP, the highest level (the third element has the smallest value) so she is placed first.

The renderings are as follows:

So it is very ‘reasonable’ (no way, who asked you to go to a senior restaurant line, to an ordinary restaurant, we will use the ordinary FIFO queue to manage the dining order).

How is the priority queue queued?

Queue: PriorityQueue: PriorityQueue: PriorityQueue: PriorityQueue: PriorityQueue: PriorityQueue: PriorityQueue

It’s too simple, inheriting Queue directly.

However, we see that the priority queue overrides the _PUT method and uses the Heappush method to put elements into the binary heap (this is a method in the heAPQ library, which also has an implementation of fetching elements).

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)
    

Copy the code

Headpush internally places the newly enqueued element directly at the end of the queue (front heap=[])

Then execute 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 the code

Here, the [least binary heap (baike.baidu.com/item/%E6%9C…) is used by constantly comparing with the parent (parentpos = (pos-1) >> 1).

If the newly added element is smaller than the parent node, the current newly added node moves up (that is, the parent node moves down to the new location each time the new node is put in).

Until it finds a location where the parent node is less than the value of the new node, it stops moving and the enqueue operation is complete.

This is a bit of a mind-numbing part, but let’s explain this entry. And then I’ll do a graph to show you.

conclusion

Priority queues, like fancy restaurants or banks VIP/VVIP, special arrangements for special people.

Internal implementation of the binary tree this data structure, after the committee to do the diagram.

The previous section of the committee said this, again put together, comparison review:

Last in, first out queues, much like supermarket containers, are seen by consumers first.

First-in, first-out line, just like everyone’s waiting for a checkup or a meal. It must be first come, first arranged.

Priority queues, like fancy restaurants or banks VIP/VVIP, special arrangements for special people.

For those who like Python, please check out the Python Basics section or the Python Getting Started to Master Section

Continuous learning and continuous development, I am Lei Xuewei! Programming is fun. The key is to get the technology right. Welcome to wechat, like support collection!