Python中的四种队列(queue)、堆(heap)

白马负金羁 2021-02-23 00:28:43
Python 队列 Queue heap 四种


Python中提供了四种内置的队列实现,特别地其中的优先级队列可以用来实现堆。此外,在Python中我们也直接使用堆。熟练掌握这些数据结构,在问题求解时可以大大简化代码的实现。文末将结合一道Leetcode题目来作为演示。

1. 普通队列(FIFO)

这是最一般的队列,核心操作有put和get,这对应了一般数据结构教材中的push和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]

执行上述代码,输出结果如下:

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


2. LIFO队列

这其实相当于一般数据结构教材中的“栈”结构,也就是后进先出。核心操作仍然是put和get(对应了push和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)

执行上述代码,输出结果如下:

LIFO [0, 5, 3]
[0]


3. 双向队列

双向队列,顾名思义,就是可以在头尾两段进行操作的队列(append, appendleft, pop, popleft)。另外,这其实是一个循环队列,因此有rotate操作来进行循环右移。

from collections import deque # 双端队列
dequeQueue = deque(['B', 'C', 'D'])
print(dequeQueue)
dequeQueue.append('E') # 在右侧插入新元素
dequeQueue.appendleft('A') # 在左侧插入新元素
print(dequeQueue)
dequeQueue.rotate(2) # 循环右移2次
print(dequeQueue)
dequeQueue.popleft() # 返回并删除队列最左端元素
print('删除最左端元素后的队列:', dequeQueue)
dequeQueue.pop() # 返回并删除队列最右端元素
print('删除最右端元素后的队列:', dequeQueue)

执行上述代码,输出结果如下:

deque(['B', 'C', 'D'])
deque(['A', 'B', 'C', 'D', 'E'])
deque(['D', 'E', 'A', 'B', 'C'])
删除最左端元素后的队列: deque(['E', 'A', 'B', 'C'])
删除最右端元素后的队列: deque(['E', 'A', 'B'])


4. 优先级队列

优先级队列——“Variant of Queue that retrieves open entries in priority order (lowest first)”,

1)注意更小的值具有更高的优先级,也就是会被最先输出:

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

执行上述代码,输出结果如下:
0
0
2
3

2)或者,可以采用tuple,其中第一个元素是优先级,第二个元素保存具体的值,例如:

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])

执行上述代码,输出结果如下:
[(0, 'D'), (1, 'E'), (2, 'F'), (3, 'G')]
D
E
F
G

3)优先级队列等价于一个堆。特别地,由于Python中的PriorityQueue中更小的值具有更高的优先级,它其实是一个最小堆。那么如何以此为基础来实现一个最大堆呢?下面给出了方案:

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])

执行上述代码,输出结果如下:

3
2
0
0

欢迎关注白马负金羁的博客 http://blog.csdn.net/baimafujinji,鉴于目前网上盗贴、洗稿等现象严重,为保证公式、图表得以正确显示,强烈建议你从该地址上查看原版博文。本博客主要关注方向包括:数字图像处理、算法设计与分析、数据结构、机器学习、数据挖掘、统计分析方法、自然语言处理。


五、堆

要创建一个堆,在Python中需要使用heapq这个包,可以通过一个函数heapify(),来把一个list转换成堆。常用的操作包括:

  • heappush(heap, item):将 item 的值加入 heap 中,保持堆的不变性。
  • heappop(heap):弹出并返回 heap 的最小的元素,保持堆的不变性。如果堆为空,抛出 IndexError 。使用 heap[0] ,可以只访问最小的元素而不弹出它。
  • heappushpop(heap, item):将 item 放入堆中,然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。
  • heapreplace(heap, item):弹出并返回 heap 中最小的一项,同时推入新的 item。 堆的大小不变。 如果堆为空则引发 IndexError。这个单步骤操作比 heappop() 加 heappush() 更高效。

注意用heapq创建的堆是一个最小堆(最小的元素总是在根结点)。如果想使用最大堆,可以参考PriorityQueue中的做法,也就是使用相反数(下面的例子中也是这样做的)。

作为一个例子,我们来看一道Leetcode编程题目(题号:295),原题描述请参考(链接)。大意就是给定一个数据流,要求出其中的中位数。思路就是将数据流平分,并维护一个最小堆(用来储存数值较大的一半数据)和一个最大堆(用来储存数值较小的一半数据)。再具体点,就是每次进来一个数,先把它存进最小堆,然后把最小堆的堆顶放进最大堆,调整两个堆,使得size差最大为1。那么根据两个堆的根,就可以很容计算中位数了。


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

作为一个思考题,如何使用PriorityQueue来改写上述代码呢? 下面给出参考答案:

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

【本文完】

2021年1月24日摄于北卡罗来纳州阿什维尔市比特摩尔庄园

 

*比特摩尔庄园(Biltmore Estate)是美国最富盛名的十大私人庄园之一,坐落于北卡罗来纳州的阿什维尔市(Ashiville),庄园周围被8000英亩森林公园环绕,还可以远眺蓝脊山脉,风景绝佳。1889年,乔治·华盛顿·范德堡二世聘请著名建筑师Richard Morris Hunt设计了该座富丽堂皇的法国文艺复兴式建筑。乔治·华盛顿·范德堡是范德堡家族在美国的第三代,他的祖父科尼利尔斯·范德堡是在19世纪末20世纪初的亿万富翁(其财富在美国历史上高居第二位)。此外,尼利尔斯·范德堡还出资捐建了今天的范德堡大学(US News常年排名在全美前二十的顶尖私立名校)。

比特摩尔庄园的主体建筑耗时六年,最终在1895年落成。庄园除了包括这座美国最大的个人住宅之外、还有花园、马场及酒坊等,每年春天,周围的花园里会有5万朵郁金香怒放。酿酒厂用自产葡萄每年可以酿制出7万箱美酒,这些葡萄酒曾先后获得过125次佳酿大奖。住宅本身建造时用砖1100万块,有大大小小250个房间、其中保龄球馆、恒温泳池、图书馆等一应俱全。房屋内还陈列了主人在周游世界时收集来的大量奇珍异宝:包括德国的丢勒、意大利的萨金特、法国的雷诺阿等大师的艺术作品1600件、来自世界13个国家的精美家具、超过两万三千册古籍图书,还有包括一口价值连城的明朝宣德青花大缸等在内的众多珍贵瓷器。

 

 

版权声明
本文为[白马负金羁]所创,转载请带上原文链接,感谢
https://baimafujinji.blog.csdn.net/article/details/113386855

  1. Python 空间绘图 - 房价气泡图绘制
  2. Translation: practical Python Programming 02_ 02_ Containers
  3. Research on Portfolio Optimization Based on particle swarm optimization
  4. Ubuntu deploying Django project
  5. Two years of Java, write Python and go without byte beating
  6. Translation: practical Python Programming 02_ 02_ Containers
  7. So learn python, grandfather learned! Introduction to super simple Python
  8. python3 多线程 与 mongo亿级消费日志数据 新鲜demo 【优化第一版】
  9. Summary of Chinese word segmentation based on Jieba
  10. I've heard it n times, but I'm not impressed. After reading this, you'll understand
  11. Summary of Chinese word segmentation based on Jieba
  12. From movie art to Python code to realize God's reverse thinking mode
  13. Summary of Chinese word segmentation based on Jieba
  14. ARIMA模型预测CO2浓度时间序列-python实现
  15. Python belongs to back-end development or front-end development? Introduction to Python!
  16. python isinstance()
  17. I've heard it n times, but I'm not impressed. After reading this, you'll understand
  18. This article will familiarize you with the transformation process of Python - & gt; cafe - & gt; om model
  19. 如何用Python一键修改上万个文件名
  20. One day quick start to Python
  21. Python 学习笔记: List
  22. 翻译:《实用的Python编程》02_03_Formatting
  23. Is there any age requirement for learning Python? Is 30 OK?
  24. Professor Tsinghua! The most complete Python tutorial in 12 hours (free sharing at the end of the article)
  25. Using Python to develop defi project
  26. Detailed explanation of Python function
  27. Python 可变类型作为函数默认参数时的副作用
  28. What do Python engineers do? What's their future?
  29. 这是我见过最好的Python教程:十分钟带你认识Python
  30. Python欢喜冤家:爬虫与反爬虫带着处理方案来给大家拜年了
  31. Python - zip() function
  32. 写Python会遇到如下的错误:ModuleNotFoundError: No module named 'email.mime'; 'email' is not a package
  33. Python类的调用以及私有和公有属性方法的调用
  34. Python类的专有方法
  35. Python基础之:数字字符串和列表
  36. How did Python pioneers evaluate this language on their 30th birthday?
  37. Python基础之:数字字符串和列表
  38. Python基础之:数字字符串和列表
  39. 窥探未来不是梦,python数据分析轻松实现
  40. This article will familiarize you with the transformation process of Python - & gt; cafe - & gt; om model
  41. 阿里、华为Python工程师总结的实用技巧,只有你还没看?
  42. 酸了!看到抖音上Python程序员晒得工资条......
  43. Python基础之:数字字符串和列表
  44. Importing excel into database adaptively by Python
  45. Python安装教程
  46. Python安装教程
  47. From Xiaobai to master, here is a guide to pandas
  48. [Python] drawing method of stem leaf diagram and compound pie diagram
  49. Drawing of Python geoplot spatial kernel density estimation map
  50. Python Seaborn economist's classic chart imitation
  51. Python space drawing - regionmask mask operation example
  52. Python space drawing - cartopy longitude and latitude add
  53. Python pykrige package Kriging interpolation calculation and visual rendering
  54. Python batch resampling, mask, slope extraction
  55. Python - Analysis of reachable circle of multiple traffic modes
  56. Python space drawing bubble drawing
  57. Python 3 multithreading and Mongo 100 million consumption log data fresh demo
  58. ARIMA model for predicting time series of CO2 concentration
  59. python isinstance()
  60. How to modify tens of thousands of file names with one key in Python