Python数据结构与算法——第三十九课 大顶堆实现优先队列

 

  优先队列和普通队列不同,优先队列是优先级高的元素先出队,然后才到优先级低的。用优先级作为大顶堆的规则参数,每次都是堆顶出队,就可以实现优先队列。

  程序代码(文本代码附录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()