Python There are four built-in queue implementations available in , In particular, the priority queue can be used to implement heap . Besides , stay Python We also use the heap directly in the . Master these data structures , It can greatly simplify the implementation of the code when solving the problem . At the end of the article, we will combine Leetcode As a demonstration .

1. Normal queue （FIFO）

This is the most general queue , The core operations are put and get, This corresponds to push and pop.

from queue import Queue
q = Queue()
q.put(0)
q.put(5)
q.put(3)
print('FIFO', q.queue) # [0, 5, 3]
head = q.get()
print(head)
print(q.queue) # [5, 3]

Execute the above code , The output is as follows ：

FIFO deque([0, 5, 3])
0
deque([5, 3])

2. LIFO queue

This is actually equivalent to the general data structure textbook “ Stack ” structure , That is, last in, first out . The core operation is still put and get（ Corresponding push and pop）.

from queue import LifoQueue
lifoQueue = LifoQueue()
lifoQueue.put(0)
lifoQueue.put(5)
lifoQueue.put(3)
print('LIFO', lifoQueue.queue)
lifoQueue.get()
lifoQueue.get()
print(lifoQueue.queue)

Execute the above code , The output is as follows ：

LIFO [0, 5, 3]
[0]

3. The bidirectional queue

The bidirectional queue , seeing the name of a thing one thinks of its function , It is a queue that can be operated in the first and last segments （append, appendleft, pop, popleft）. in addition , This is actually a circular queue , So there is rotate Operation to cycle right .

from collections import deque # deque
dequeQueue = deque(['B', 'C', 'D'])
print(dequeQueue)
dequeQueue.append('E') # Insert a new element on the right
dequeQueue.appendleft('A') # Insert new element on the left
print(dequeQueue)
dequeQueue.rotate(2) # Cycle moves to the right 2 Time
print(dequeQueue)
dequeQueue.popleft() # Return and delete the leftmost element of the queue
print(' The queue after deleting the leftmost element ：', dequeQueue)
dequeQueue.pop() # Return and delete the rightmost element of the queue
print(' The queue after deleting the rightmost element ：', dequeQueue)

Execute the above code , The output is as follows ：

deque(['B', 'C', 'D'])
deque(['A', 'B', 'C', 'D', 'E'])
deque(['D', 'E', 'A', 'B', 'C'])
The queue after deleting the leftmost element ： deque(['E', 'A', 'B', 'C'])
The queue after deleting the rightmost element ： deque(['E', 'A', 'B'])

4. Priority queue

Priority queue ——“Variant of Queue that retrieves open entries in priority order (lowest first)”,

1） Note that smaller values have higher priority , That is, it will be output first ：

from queue import PriorityQueue # Priority queue
pq = PriorityQueue()
pq.put(0)
pq.put(3)
pq.put(2)
pq.put(0)
while not pq.empty():
print(pq.get())

Execute the above code , The output is as follows ：
0
0
2
3

2） perhaps , May adopt tuple, The first element is priority , The second element holds the specific value , for example ：

pq = PriorityQueue()
pq.put((0, 'D'))
pq.put((3, 'G'))
pq.put((2, 'F'))
pq.put((1, 'E'))
print(pq.queue)
while not pq.empty():
print(pq.get()[1])

Execute the above code , The output is as follows ：
[(0, 'D'), (1, 'E'), (2, 'F'), (3, 'G')]
D
E
F
G

3） A priority queue is equivalent to a heap . Specially , because Python Medium PriorityQueue Smaller values in have higher priority , It's actually the smallest pile . So how to achieve a maximum heap based on this ？ Here's the solution ：

pq = PriorityQueue()
pq.put((-0, 0))
pq.put((-3, 3))
pq.put((-2, 2))
pq.put((-0, 0))
while not pq.empty():
print(pq.get()[1])

Execute the above code , The output is as follows ：

3
2
0
0

Welcome to pay attention to Baima's blog  http://blog.csdn.net/baimafujinji, In view of the current online posting 、 The phenomenon of manuscript washing is serious , To ensure the formula 、 The chart is shown correctly , It is highly recommended that you check the original blog post from this address . The main focus of this blog includes ： digital image processing 、 Algorithm design and analysis 、 data structure 、 machine learning 、 data mining 、 Statistical analysis method 、 natural language processing .

5、 ... and 、 Pile up

To create a heap , stay Python Required in heapq This package , It can be done by a function heapify(), Let's take one list Into piles . Common operations include ：

• heappush(heap, item)： take item Add the value of heap in , Keep the heap invariant .
• heappop(heap)： Pop up and return heap The smallest element of , Keep the heap invariant . If the heap is empty , Throw out IndexError . Use heap[0] , You can access only the smallest element without popping it up .
• heappushpop(heap, item)： take item Put in a pile , And then pop up and go back heap The smallest element of . The combined operation calls... Before heappush() Call again heappop() Run more efficiently .
• heapreplace(heap, item)： Pop up and return heap The smallest of all , And push in New item. The size of the heap doesn't change . If the heap is empty, then IndexError. This one-step operation is better than heappop() Add heappush() More efficient .

Use it carefully heapq The heap created is the smallest heap （ The smallest element is always at the root ）. If you want to use the largest heap , You can refer to PriorityQueue In the practice , That is to say, use the opposite number （ This is also the case in the following example ）.

As an example , Let's take a look at Leetcode Programming topics （ Question no ：295）, Please refer to （ link ）. Given a data stream , Ask for the median . The idea is to divide the data stream equally , And maintain a minimal heap （ It's used to store half of the larger data ） And one of the biggest piles （ It's used to store half of the smaller data ）. More specifically , It's one count at a time , Put it in the minimum heap first , Then put the top of the smallest pile into the largest pile , Adjust the two heaps , bring size The biggest difference is 1. So according to the roots of the two piles , It's easy to calculate the median .

from heapq import *
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.max_h = list()
self.min_h = list()
heapify(self.max_h)
heapify(self.min_h)
def addNum(self, num: int) -> None:
heappush(self.min_h, num)
heappush(self.max_h, -heappop(self.min_h))
if len(self.max_h) > len(self.min_h):
heappush(self.min_h, -heappop(self.max_h))
def findMedian(self) -> float:
max_len = len(self.max_h)
min_len = len(self.min_h)
if max_len == min_len:
return (self.min_h[0] + -self.max_h[0]) / 2.0
else:
return self.min_h[0] / 1.0

As a thinking question , How to use PriorityQueue To rewrite the above code ？ Here is the reference answer ：

from queue import PriorityQueue
class MedianFinder:
def __init__(self):
self.max_h = PriorityQueue()
self.min_h = PriorityQueue()
def addNum(self, num: int) -> None:
self.min_h.put(num)
self.max_h.put(-self.min_h.get())
if len(self.max_h.queue) > len(self.min_h.queue):
self.min_h.put(-self.max_h.get())
def findMedian(self) -> float:
max_len = len(self.max_h.queue)
min_len = len(self.min_h.queue)
if max_len == min_len:
return (self.min_h.queue[0] + -self.max_h.queue[0]) / 2.0
else:
return self.min_h.queue[0] / 1.0

【 The end of this paper 】

* Bitmore manor （Biltmore Estate） It is one of the ten most famous private estates in the United States , Asheville, North Carolina （Ashiville）, The manor was surrounded by 8000 Acres of forest park around , You can also overlook the Blue Ridge Mountains , The scenery is excellent .1889 year , George · Washington · Van der Bauer II employs famous architects Richard Morris Hunt Designed the magnificent French Renaissance architecture . George · Washington · Vanderberg is the third generation of the Vanderberg family in the United States , His grandfather Cornelius · Vanderberg is in 19 The end of the century 20 The billionaires of the early 20th century （ Its wealth ranks second in American history ）. Besides , Nellies · Vanderberg also contributed to the construction of today's Vanderberg University （US News The top 20 private schools in the United States ）.

The main building of bitmore manor took six years , In the end in 1895 It was completed in . The estate includes the largest individual residence in the United States 、 And the garden 、 Racecourse and wine shop, etc , Every spring , There will be... In the garden around 5 Ten thousand tulips in full bloom . Wineries can produce... Every year from their own grapes 7 Ten thousand cases of wine , These wines have been acquired successively 125 This is a great wine award . The house itself was built with bricks 1100 Ten thousand pieces , It's big and small 250 A room 、 One of them is the bowling alley 、 Constant temperature swimming pool 、 Libraries and everything . The house also displays a large number of treasures collected by the owner when traveling around the world ： Including Durer in Germany 、 Sargent of Italy 、 Works of art by French masters like Renoir 1600 Pieces of 、 From the world 13 Beautiful furniture of a country 、 More than 23000 ancient books , There are also many precious porcelains, including a blue and white VAT in Xuande of Ming Dynasty, which is of great value .