Python中的优先队列(priority queue)和堆(heap)
作者:笨笨的蛋 发布时间:2023-11-22 05:40:03
队列和优先队列(Priority Queue)
队列是一种可以完成插入和删除的数据结构。普通队列是先进先出(FIFO), 即先插入的先被删除。
然而在某些时候我们需要按照任务的优先级顺序来决定出队列的顺序,这个时候就需要用到优先级队列了。优先队列是一种可以完成插入和删除最小元素的数据结构
python中有现成的优先队列类可以调用。
代码示例
from queue import Queue # 队列,FIFO
from queue import PriorityQueue #优先级队列,优先级高的先输出
###############队列(Queue)的使用,/python中也可是用列表(list)来实现队列###############
q = Queue(maxsize) #构建一个队列对象,maxsize初始化默认为零,此时队列无穷大
q.empty()#判断队列是否为空(取数据之前要判断一下)
q.full()#判断队列是否满了
q.put()#向队列存放数据
q.get()#从队列取数据
q.qsize()#获取队列大小,可用于判断是否满/空
###用法示例:
>>> q = Queue(3)
>>> for i in range(3):
>>>q.put(i)
>>> q.full()
True
>>> while not q.empty():
>>> print(q.get())
0
1
2
###############优先队列(PriorityQueue)的使用###############
"""
队列的变体,按优先级顺序(最低优先)检索打开的条目。
条目通常是以下格式的元组:
插入格式:q.put((priority number, data))
特点:priority number 越小,优先级越高
其他的操作和队列相同
"""
>>> q = PriorityQueue()
>>> q.put((2, "Lisa"))
>>> q.put((1, "Lucy"))
>>> q.put((0, "Tom"))
>>> i = 0
>>> while i < q.qsize():
>>> print(q.get())
(0,"Tom")
(1,"Lucy")
(2,"Lisa")
#可见并没有按照输入的顺序输出的,而是按照优先级顺序输出的
#优先独队列的实质是
堆(heap)
看完上面的示例我们也许会有疑惑,优先队列是如何来实现的了?
----------优先队列的实质是每次插入时按照一定的规则插入,删除时直接找到最小的那个元素弹出即可。插入和弹出最坏情况下的时间复杂度都是O(LogN)
下面我们就来介绍实现优先队列的一种数据结构——堆(heap)。
简介
堆的实质是一个完全二叉树(除最底层外,其余层都是满二叉树,且最底层的节点从左往右顺序排列)。 堆主要分为大顶堆和小顶堆两种
1.大顶堆:每个分支的根节点都大于等于其子节点。(ki >= k2i)and (ki >= k2i+1)
2.小顶堆:每个分支的根节点都小于等于其子节点。(ki <= k2i)and (ki <= k2i+1)
所以堆中的第i个元素的父亲是floor(i/2)(向下取整), 第i个元素的左右孩子分别是2i和2i+1
堆的根节点要从1开始计算,不能从0开始计算。(假如从零开始i=2时其父亲节点为floor(2/2)=1, 显然是错误的)
初始化构建堆
将一个有k个元素的数组构成一个大顶堆或者小顶堆。时间复杂度O(n)$
核心思路:从下往上,从右往左,且每次都从第floor(k/2)个元素开始进行调整依次递减直到根节点
1.从floor(k/2)个元素开始进行调整,调整完毕,则i--;
#调整节点,每次只调整该根节点以下的子树
while i <= k
1.1 找出左右孩子中最大的那个
1.2 该节点和较大的那个子节点比较,
如果父节点较大,break
如果子节点较大,记录子节点的索引,把子节点的值给父节点
1.3 将上面较大的那个字节点作为新的父节点开始一轮循环
循环结束后,将父节点的值放到他应该去的子节点的位置上
例如有如下数组
把其转化成完全二叉树的形式就是
该数组一共有9个元素,所以从i = floor(9/2)=4 个元素开始,第4个元素是6, 其右孩子9最大,将6和9交换完成一次调整.
i=3,第三个元素是8,8比左右孩子都大,不用交换
i=2,此时的子树是:第二个元素是2,而此时以2为根节点的子树如下左图。交换过程为: a).2与9交换,此时的根节点就到了2现在的位置 (下中图)。b).2与7交换。 c)交换完成,本次调整完毕
i=1,此时的父节点就是整棵树的根节点,而此时整棵树的状态是下图所示
a). 5和9交换,此时5到了9的位置(下左图) b). 5和7交换,5到了7的位置(下中图) c).最后5和6交换,完成调整。
经过以上的floor(k/2)次的调整之后,由一个无序数组初始化构建大顶堆就完成了
堆的插入(节点上浮)
时间复杂度O(log(k+1))
我们之前由一个无序数组构造了一个大顶堆,那么现在我们要插入一个新的元素该怎么办了,如下图,如果直接在最末尾插入,则破坏了堆的结构,所以还需要按进行调整。
调整规则:由于其他子树的顺序都已经调整完毕,所以只需要调整根节点到插入节点所在的子路即可。
如下图所示。(a)将11与4调整,(b)将11与7调整,©再将11与9调整。最后得到调整完毕的结果。
堆的删除(节点下浮)
时间复杂度O(log(k-1))
由于堆是队列结构,只能从堆中删除堆顶的元素。移除堆顶元素之后,之前的完全二叉树就变成来两个子树,次数最方便的做法就是用堆的最后一个节点来填补取走的堆顶元素,并将堆的实际元素个数减1。但是这样做以后又不满足堆的定义了,还是要进行调整。
调整规则:从根节点开始逐层向下调整即可。
(a).将5与8调换,(b)调整完成,删除完毕
堆的应用
之间讲过的利用堆(python中是小顶堆)来实现优先队列
利用堆求Top k:
假如现在有1亿个数据要求其中前十个最小的元素。最笨方法就是对所有数据进行排序,然后找出前十个最小的,即使使用快排,也需要O(NlogN)的时间复杂度。假如利用大顶堆的话–先利用前10个数据构造一个大顶堆,然后顺序遍历数组与大顶堆顶点比较,假如比大于等于顶点直接删除,否则就删除堆顶点并插入新的节点,最后堆里面的元素就是最小的前是个元素。这样求出来的时间复杂度为Nlog(k)
假如要求前十个最大的元素,那就要使用小顶堆来实现
最后放上python手动实现将数组转化为大顶堆和小顶堆的代码
class Heap:
def __init__(self, _list):
self._list = _list
self.k = len(_list)
def _bigHeapAdjuest(self, j):
temp = self._list[j] #存放当前双亲节点的值,j代表当前节点的位置
i = 2*j #j的左孩子
while i <= self.k:
if i < self.k and self._list[i] < self._list[i+1]: #i==n时由于只有一个子节点,所以没有比较的必要
i += 1
#与双亲比较,如果双亲大则跳过
#如果双亲小,就把大的给双亲
if temp >= self._list[i]:
break #没有必要修整
self._list[j] = self._list[i] #元素交换
j = i #j记录着temp应该去的位置,由于这个位置的节点发生了变动,所以需要再次调整
i *= 2 #接着找该节点的左孩子
self._list[j] = temp
def _smallheapAdjuest(self, j):
temp = self._list[i] #父节点
i = 2*j #左孩子
while i <= self.k:
if i < self.k and self._list[i] > self._list[i+1]: #找最小的那个孩子
i += 1
#构建小顶堆,小于父节点的都要上浮
if self._list[i] >= temp:
break
self._list[j] = self._list[i] #子节点交给父节点
j= i #记录父节点应该去的索引位置
i *= 2
self._list[j] = temp
def heapSort(self):
self._list.insert(0, -1)
s = self.length // 2
#构建大顶堆
for j in range(s, 0, -1):
self._bigHeapAdjuest(j)
#构建小顶堆
for j in range(s, 0, -1):
self._SmallheapAdjuest(j)
来源:https://blog.csdn.net/qq_39463274/article/details/105414188
猜你喜欢
- 用window.open打开的窗口中,有时候session变量会丢掉,给asp编程带来的一定的麻烦。用参数传递解决它:<DIV&nbs
- 防止用户通过后退按钮重复提交表单 <% response.Buffer=true response.Expires=0 respons
- 引言上一篇文章中引入了消息队列对秒杀流量做削峰的处理,我们使用的是Kafka,看起来似乎工作的不错,但其实还是有很多隐患存在,如果这些隐患不
- 前言使用 Pandas 的between 、cut、qcut 和 value_count离散化数值变量。分箱是一种常见的数据预处理技术有时也
- 近日在月影的blog上找到一段代码。看了老半天没明白什么意思,倍受打击!不死心,于是仔细分析思考了好几次,才明白过来这段函数的意义。js果然
- 郁闷的事来了,先看前台HTML: 购买数量: <input id="txtNum" type="text
- 工作中遇到一个很棘手的问题,交互设计师和视觉设计师在做出高保真原型后提交给前端开发工程师,最后得到的web产物从细节上和布局上都和高保真原型
- 自去年以来,我们正在开发区块链(Blockchain)业务。最近使用过Ethereum并使用PHP,所以我想我们应该聊聊这个话题。这里有个前
- 在小飞的博客上看到他写了一篇关于reset.css的文章,文章中关于css的部分分析的非常不错,但对于文中关于强调把CSS分别配置,对每一个
- 前几天光耀童鞋喷了一篇《谈网站注册、登录过程》,今天我们在与小爬童鞋梳理购买流程的时候也谈到了这部分内容。其实注册作为一个网站基本功能再普通
- 使用cookie来判断来访者身份,是否是首次登陆, asp代码实例如下:< %@ LANGUAGE=&q
- 本文中我们将通过一个例子来介绍SQL Server 2005的一个Bug,首先,在建立同义词链接Oracle的时候,我们会使用下面的语句:C
- 声明定位元素:position属性值设置除默认值static以外的元素,包括relative,absolute,fixed。平台:win/I
- 本文由 kouyubo 整理到现在为止,只有一些已经工作的特性,他们中的一些如下:圆角从web2.0开始,开始流行使用圆角,如果你不使用圆角
- 什么是 go-cachego-cache 是一个轻量级的基于内存的 K-V 储存组件,内部实现了一个线程安全的 map[strin
- 一.目标浏览网页的时候,看见哪个元素,就能截取哪个元素当图片,不管那个元素有多长 二.所用工具和第三方库python ,PIL,s
- 各种asp字符串处理函数,包括:把字符串换为char型数组,把一个数组转换成一个字符串,检查源字符串str是否以chars开头,检查源字符串
- 要实现此效果需要 1 个步骤: 第 1 步: 把下面的代码加到<BODY></BODY&g
- 如下所示://定义编码 header( 'Content-Type:text/html;charset=utf-8
- 不同于行级或页级锁定的选项:· 版本(例如,为并行的插入在MySQL中使用的技术),其中可以一个写操作,同时有许多读取操作。这明数据库或表支