优先队列和普通队列不同,优先队列是优先级高的元素先出队,然后才到优先级低的。用优先级作为大顶堆的规则参数,每次都是堆顶出队,就可以实现优先队列。
程序代码(文本代码附录1):
运行结果:
练习题1:请修改上面的程序,使优先级低的先出队。
学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com,开展学编程三部曲:
Scratch(三年级以前)>>>Python(四年级以后)>>>C++(七年级以后)教育实验活动,任何人可以免费参加,打开https://xuesiying.stem86.com网页注册进入课堂,也可关注本公众号留言。
更多课程请打开“学思营”同步网站:
http://www.5xstar.com/doc.html
参考资料:
1、《Python算法图解》何韬编著 清华大学出版社
附录1:
#大(小)顶堆实现优先队列
#优先队列节点类
class PQNode:
def __init__(self, serialNumber, priority=0):
self.serialNumber=serialNumber #系列号,不重复
self.priority=priority #优先级
#优先队列类
class TopHeapPriorityQueue:
def __init__(self, isMax = True):
self.body = [] #顶堆列表
self.isMax = isMax #是否大顶堆
def add(self,node): #加入节点
self.body.append(node)
n = len(self.body) - 1 #要检查的下标,最后加入的节点
self.adjust(n)
def adjust(self, n): #调整新加入节点
if n>0:
fatherN = (n-1)//2
if self.checkChange(n, fatherN): #如果交换了值,递归调用
self.adjust(fatherN)
def checkChange(self, n, fatherN): #检查和交换节点值
change = False
if self.isMax: #大顶堆
if self.body[n].priority > self.body[fatherN].priority:
change = True
else: #小顶堆
if self.body[n].priority < self.body[fatherN].priority:
change = True
if change: #需要交换
temp = self.body[fatherN]
self.body[fatherN] = self.body[n]
self.body[n] = temp
return True
return False
def levelDisplay(self): #分层显示
slen = len(self.body)
if slen == 0:
print(None)
return
for n in range(slen): #n层数一定不超过节点数,从0开始
start = pow(2, n) - 1 #开始下标,包括
isFinished = True #是否完成,默认已完成
if start < slen: #如果开始下标没超过结束点
stop = pow(2, n+1) -1 #结束下标,不包括
if stop > slen: #结束下标已超过结束点加1
stop = slen #结束下标变更为结束点加1
else:
isFinished = False #还没到结束点所在层
for i in range(start, stop): #打印当前层节点
item = self.body[i]
print("%d(%d)" % (item.priority, item.serialNumber), end = "\t")
print("")
if isFinished:
break
def remove(self, sn): #删除元素
n = self.findNode(sn) #定位下标
if n != None:
slen = len(self.body)
last = self.body[slen-1] #缓存最后一个元素
self.body = self.body[:slen-1] #缩堆
if n < slen - 1:
self.removeNode(n, last, slen-2) #删除节点
def findNode(self, sn): #查找下标
slen = len(self.body)
if slen == 0: #堆中无元素
return None
for i in range(slen): #从第0个数开始检查删除位置
if self.body[i].serialNumer == sn:
return i
return None
def removeNode(self, n, last, end, isFirst = True): #删除节点
'''@n节点下标@last最后元素值@end结束下标@isFirst是否入口调用,递归False'''
cflag, left, right = self.findChild(n, end) #查询子节点情况
if cflag == 0: #叶节点,用最后节点代替后调整,完成
self.body[n] = last
if isFirst: #如果是入口调用
self.adjust(n)
return
elif cflag == 1: #只有左子叶,用左子叶代替,递归
nn = left
elif cflag == 2: #只有右子叶,用右子叶代替,递归
nn = right
else: #左右子叶都有,用顶者代替,递归
nn = self.getTop(left, right) #获取左右子中顶者
if self.isOrder(last, self.body[nn]): #是否符合规则,最后元素值大(小)
self.body[n] = last
if isFirst: #如果是入口调用
self.adjust(n)
return
self.body[n] = self.body[nn] #往下递归
self.removeNode(nn,last,end,False)
def findChild(self, n, end): #查找待删除节点的左右子情况
cflag = 0 #0表示没子,1表示有左子,2表示有右子,3表示有左右子
left = 2*n + 1
if left <= end: #左指针
cflag += 1
right = 2*n + 2
if right <= end: #右指针
cflag += 2
return cflag, left, right
def getTop(self, left, right): #获取左右中最值下标
if self.isMax:
if self.body[right].priority < self.body[left].priority or \
(self.body[right].priority == self.body[left].priority and \
self.body[right].serialNumber > self.body[left].serialNumber): #号码小先出队
return left
else:
return right
else:
if self.body[right].priority > self.body[left].priority or \
(self.body[right].priority == self.body[left].priority and \
self.body[right].serialNumber > self.body[left].serialNumber): #号码小先出队
return left
else:
return right
def isOrder(self, node1, node2): #规则检查,node2优先
if self.isMax:
if node1.priority > node2.priority or \
(node1.priority == node2.priority and \
node1.serialNumber < node2.serialNumber):
return True
else:
return False
else:
if node1.priority < node2.priority or \
(node1.priority == node2.priority and \
node1.serialNumber < node2.serialNumber):
return True
else:
return False
def pop(self): #弹出顶元素
slen = len(self.body)
if slen == 0:
return None
top = self.body[0]
if slen == 1: #堆中只有一个元素
self.body = []
else:
last = self.body[slen-1] #缓存最后一个元素
self.body = self.body[:slen-1] #缩堆
self.removeNode(0, last, slen-2) #删除节点
return top
#测试
if __name__ == "__main__":
from random import randint
heap = TopHeapPriorityQueue()
for sn in range(1, 21):
node = PQNode(sn, randint(0,9))
heap.add(node)
print("Pop前分层遍历:")
heap.levelDisplay()
for i in range(1, 21):
v = heap.pop()
print("Pop%d(%d)后分层遍历:"%(v.priority,v.serialNumber))
heap.levelDisplay()