Four kinds of queues and heaps in Python

kinds queues heaps python


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 】

2021 year 1 month 24 Sun shot at bitmore estate, Asheville, North Carolina

 

* 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 .

 

 

版权声明
本文为[The white horse bears the golden yoke]所创,转载请带上原文链接,感谢
https://pythonmana.com/2021/02/20210223002809775t.html

  1. Python 学习笔记: List
  2. 翻译:《实用的Python编程》02_03_Formatting
  3. Is there any age requirement for learning Python? Is 30 OK?
  4. Professor Tsinghua! The most complete Python tutorial in 12 hours (free sharing at the end of the article)
  5. Using Python to develop defi project
  6. Detailed explanation of Python function
  7. Python 可变类型作为函数默认参数时的副作用
  8. What do Python engineers do? What's their future?
  9. 这是我见过最好的Python教程:十分钟带你认识Python
  10. Python欢喜冤家:爬虫与反爬虫带着处理方案来给大家拜年了
  11. Python - zip() function
  12. 写Python会遇到如下的错误:ModuleNotFoundError: No module named 'email.mime'; 'email' is not a package
  13. Python类的调用以及私有和公有属性方法的调用
  14. Python类的专有方法
  15. Python基础之:数字字符串和列表
  16. How did Python pioneers evaluate this language on their 30th birthday?
  17. Python基础之:数字字符串和列表
  18. Python基础之:数字字符串和列表
  19. 窥探未来不是梦,python数据分析轻松实现
  20. This article will familiarize you with the transformation process of Python - & gt; cafe - & gt; om model
  21. 阿里、华为Python工程师总结的实用技巧,只有你还没看?
  22. 酸了!看到抖音上Python程序员晒得工资条......
  23. Python基础之:数字字符串和列表
  24. Importing excel into database adaptively by Python
  25. Python安装教程
  26. Python安装教程
  27. From Xiaobai to master, here is a guide to pandas
  28. [Python] drawing method of stem leaf diagram and compound pie diagram
  29. Drawing of Python geoplot spatial kernel density estimation map
  30. Python Seaborn economist's classic chart imitation
  31. Python space drawing - regionmask mask operation example
  32. Python space drawing - cartopy longitude and latitude add
  33. Python pykrige package Kriging interpolation calculation and visual rendering
  34. Python batch resampling, mask, slope extraction
  35. Python - Analysis of reachable circle of multiple traffic modes
  36. Python space drawing bubble drawing
  37. Python 3 multithreading and Mongo 100 million consumption log data fresh demo
  38. ARIMA model for predicting time series of CO2 concentration
  39. python isinstance()
  40. How to modify tens of thousands of file names with one key in Python
  41. Python notes: List
  42. Translation: practical Python Programming 02_ 03_ Formatting
  43. Python中的四种队列(queue)、堆(heap)
  44. Side effects of Python mutable types as default parameters of functions
  45. This is the best Python tutorial I've ever seen: ten minutes to get to know python
  46. 使用python编写量子线路打印的简单项目,并使用Sphinx自动化生成API文档
  47. Python happy enemy: crawler and anti crawler with a solution to give you New Year
  48. 使用python编写量子线路打印的简单项目,并使用Sphinx自动化生成API文档
  49. When writing python, you will encounter the following error: modulenotfounderror: no module named ' email.mime '; 'email' is not a package
  50. Python class call and private and public property method call
  51. Proprietary methods for Python classes
  52. Foundation of Python: number string and list
  53. Foundation of Python: number string and list
  54. Foundation of Python: number string and list
  55. 华为 Python网络自动化
  56. Python Cannot open E:\Python36\Scripts\pip-script.py
  57. Peeping into the future is not a dream, python data analysis is easy to achieve
  58. The practical skills summed up by Alibaba and Huawei Python engineers, only you haven't seen them yet?
  59. Sour! See the Python programmers on the tiktok get the pay slip...
  60. Foundation of Python: number string and list