“This is the 16th 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.

The previous article showed priority queues in a restaurant scenario and quickly explained the logic behind priority queue removal (using binary heaps).

Outgoing queue of priority queue

Do you remember how to find a queue?

As shown in the figure below, this is the get method of the queue parent class Queue.Queue (to fetch the elements of the queue).

Call PriorityQueue’s _get method in get method (because subclass PriorityQueue overrides it)

Here is the method _GET called by the priority queue dequeue operation

def _get(self):
    return heappop(self.queue)
Copy the code

The binary heap is used again, and we continue to look at its implementation:

def heappop(heap):
    lastelt = heap.pop()    
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
    return lastelt
Copy the code

Methods:

Line 1: Pop elements directly from the list. When the entire priority queue is empty, the program immediately reports an error. The reader can generate a list object separately, directly pop. That is’ []. Pop () ‘)

Line 2: Continue to check if the list heap (which maintains a binary heap structure) is empty, if so, run the last line (return the last element of the list), and the statement inside if is not executed. This means that there is only one element in the current list, which is the easiest.

Otherwise (starting at line 3), the binary tree needs to be dynamically balanced for execution judgment. There are two main steps:

• The first step is that we directly remove the top node of the binary tree. The element at the top of the smallest heap has the lowest priority value and the highest priority level, so it is correct to directly take it.
• The second step is to replace the top element with the last element added, connecting the remaining two subtrees directly. But the binary tree is not the least binary heap, so that’s where the following method comes in.

For easy parsing, post _siftup source code directly here, readers can quickly read:

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)
Copy the code

The first three lines in the method determine the substarting position, the upper left element position (childpos), and the top element newitem.

Enter the loop, where the exit condition is whether the left child node position => the length of the rest of the list. Because the elements are always placed from left to right in each layer.

If we look inside the loop, the left node of the binary tree is 2pos+1, and the right node is (2pos+1) +1.

This line of code, ‘Rightpos < endpos and not heap[childpos] < heap[rightpos]’, ensures that within the boundary always:

Heap [pos] = heap[childpos]), that is, the smaller value in the left and right nodes is increased to the root of the node to ensure that the subsequent subtrees meet the minimum binary heap condition.

Until there is no subsequent leaf node alignment. This is equivalent to taking the side minimum and putting it at the top to perform the _siftDown method, which was explained in the previous article.

conclusion

Priority queue, using the minimum binary heap as the core, to achieve efficient queue and queue.

The efficiency mentioned here is mainly the use of binary tree structure to process incoming and outgoing queues, without the need to traverse the entire list each time (the specific operation efficiency will be shown in the next section).

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!