Python优先队列（priorityqueue）和堆（heap）
队列和优先队列（Priority Queue）
队列是⼀种可以完成插⼊和删除的数据结构。普通队列是先进先出（FIFO), 即先插⼊的先被删除。
然⽽在某些时候我们需要按照任务的优先级顺序来决定出队列的顺序，这个时候就需要⽤到优先级队列了。优先队列是⼀种可以完成插⼊和删除最⼩元素的数据结构
python中有现成的优先队列类可以调⽤。
代码⽰例
from queue import Queue # 队列，FIFO
from queue import PriorityQueue #优先级队列，优先级⾼的先输出
>>>队列（Queue）的使⽤，/python中也可是⽤列表（list）来实现队列>>>
q = Queue(maxsize) #构建⼀个队列对象，maxsize初始化默认为零，此时队列⽆穷⼤
q.full() #判断队列是否满了
q.put() #向队列存放数据
<() #从队列取数据
q.qsize() #获取队列⼤⼩，可⽤于判断是否满/空
###⽤法⽰例：
>>> q = Queue(3)
>>> for i in range(3):
>>> q.put(i)
>>> q.full()
True
>>> while pty():
>>> ())
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()：
>>> ())
(0，"Tom")
(1，"Lucy")
(2，"Lisa")
#可见并没有按照输⼊的顺序输出的，⽽是按照优先级顺序输出的
#优先独队列的实质是
堆（heap）
看完上⾯的⽰例我们也许会有疑惑，优先队列是如何来实现的了？
----------优先队列的实质是每次插⼊时按照⼀定的规则插⼊，删除时直接到最⼩的那个元素弹出即可。插⼊和弹出最坏情况下的时间复杂度都是O(LogN)
下⾯我们就来介绍实现优先队列的⼀种数据结构——堆(heap)。
简介
堆的实质是⼀个完全⼆叉树(除最底层外，其余层都是满⼆叉树，且最底层的节点从左往右顺序排列)。 堆主要分为⼤顶堆和⼩顶堆两种
1.⼤顶堆：每个分⽀的根节点都⼤于等于其⼦节点。（k >= k ）and (k >= k )
2.⼩顶堆：每个分⽀的根节点都⼩于等于其⼦节点。（k <= k ）and (k <= k )
所以堆中的第i个元素的⽗亲是floor(i/2)（向下取整）, 第i个元素的左右孩⼦分别是2i和2i+1
堆的根节点要从1开始计算，不能从0开始计算。(假如从零开始i=2时其⽗亲节点为floor(2/2)=1, 显然是错误的)python 定义数组
初始化构建堆
将⼀个有k个元素的数组构成⼀个⼤顶堆或者⼩顶堆。时间复杂度O(n)$
核⼼思路：从下往上，从右往左，且每次都从第floor(k/2)个元素开始进⾏调整依次递减直到根节点
1.从floor(k/2)个元素开始进⾏调整，调整完毕，则i--；
#调整节点，每次只调整该根节点以下的⼦树
while i <= k
1.1 出左右孩⼦中最⼤的那个
1.2 该节点和较⼤的那个⼦节点⽐较，
如果⽗节点较⼤，break
如果⼦节点较⼤，记录⼦节点的索引，把⼦节点的值给⽗节点
1.3 将上⾯较⼤的那个字节点作为新的⽗节点开始⼀轮循环
循环结束后，将⽗节点的值放到他应该去的⼦节点的位置上
例如有如下数组
把其转化成完全⼆叉树的形式就是
1.
该数组⼀共有9个元素，所以从i = floor(9/2)=4 个元素开始，第4个元素是6, 其右孩⼦9最⼤，将6和9交换完成⼀次调整.
2.
i=3，第三个元素是8,8⽐左右孩⼦都⼤，不⽤交换
3. i=2，此时的⼦树是：第⼆个元素是2,⽽此时以2为根节点的⼦树如下左图。交换过程为: a).2与9交换，此时的根节点就到了2现在的位i 2i i 2i+1i 2i i 2i+1
3. i=2，此时的⼦树是：第⼆个元素是2,⽽此时以2为根节点的⼦树如下左图。交换过程为: a).2与9交换，此时的根节点就到了2现在的位
置 (下中图)。b).2与7交换。 c)交换完成，本次调整完毕
4. 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)调整完成，删除完毕
堆的应⽤
1. 之间讲过的利⽤堆(python中是⼩顶堆)来实现优先队列
2. 利⽤堆求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)
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
python标准库和扩展库
« 上一篇
Python编程分布式技巧
下一篇 »
发表评论