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爬虫获取招聘网站职位信息
  2. Using Python crawler to obtain job information of recruitment website
  3. Several highly rated Python libraries arrow, jsonpath, psutil and tenacity are recommended
  4. Python装饰器
  5. Python实现LDAP认证
  6. Python decorator
  7. Implementing LDAP authentication with Python
  8. Vscode configures Python development environment!
  9. In Python, how dare you say you can't log module? ️
  10. 我收藏的有关Python的电子书和资料
  11. python 中 lambda的一些tips
  12. python中字典的一些tips
  13. python 用生成器生成斐波那契数列
  14. python脚本转pyc踩了个坑。。。
  15. My collection of e-books and materials about Python
  16. Some tips of lambda in Python
  17. Some tips of dictionary in Python
  18. Using Python generator to generate Fibonacci sequence
  19. The conversion of Python script to PyC stepped on a pit...
  20. Python游戏开发,pygame模块,Python实现扫雷小游戏
  21. Python game development, pyGame module, python implementation of minesweeping games
  22. Python实用工具,email模块,Python实现邮件远程控制自己电脑
  23. Python utility, email module, python realizes mail remote control of its own computer
  24. 毫无头绪的自学Python,你可能连门槛都摸不到!【最佳学习路线】
  25. Python读取二进制文件代码方法解析
  26. Python字典的实现原理
  27. Without a clue, you may not even touch the threshold【 Best learning route]
  28. Parsing method of Python reading binary file code
  29. Implementation principle of Python dictionary
  30. You must know the function of pandas to parse JSON data - JSON_ normalize()
  31. Python实用案例,私人定制,Python自动化生成爱豆专属2021日历
  32. Python practical case, private customization, python automatic generation of Adu exclusive 2021 calendar
  33. 《Python实例》震惊了,用Python这么简单实现了聊天系统的脏话,广告检测
  34. "Python instance" was shocked and realized the dirty words and advertisement detection of the chat system in Python
  35. Convolutional neural network processing sequence for Python deep learning
  36. Python data structure and algorithm (1) -- enum type enum
  37. 超全大厂算法岗百问百答(推荐系统/机器学习/深度学习/C++/Spark/python)
  38. 【Python进阶】你真的明白NumPy中的ndarray吗?
  39. All questions and answers for algorithm posts of super large factories (recommended system / machine learning / deep learning / C + + / spark / Python)
  40. [advanced Python] do you really understand ndarray in numpy?
  41. 【Python进阶】Python进阶专栏栏主自述:不忘初心,砥砺前行
  42. [advanced Python] Python advanced column main readme: never forget the original intention and forge ahead
  43. python垃圾回收和缓存管理
  44. java调用Python程序
  45. java调用Python程序
  46. Python常用函数有哪些?Python基础入门课程
  47. Python garbage collection and cache management
  48. Java calling Python program
  49. Java calling Python program
  50. What functions are commonly used in Python? Introduction to Python Basics
  51. Python basic knowledge
  52. Anaconda5.2 安装 Python 库(MySQLdb)的方法
  53. Python实现对脑电数据情绪分析
  54. Anaconda 5.2 method of installing Python Library (mysqldb)
  55. Python implements emotion analysis of EEG data
  56. Master some advanced usage of Python in 30 seconds, which makes others envy it
  57. python爬取百度图片并对图片做一系列处理
  58. Python crawls Baidu pictures and does a series of processing on them
  59. python链接mysql数据库
  60. Python link MySQL database