Python中优先队列的实现

writer：lIcht                      email：lIcht.gzl@gmail.com                 date:  2019.9.22

        优先队列是一种类似于队列和栈的数据结构，与之根本的区别是后者的存取顺序是进入队列或者栈的时间顺序来确定的，但是优先队列的出入操作是根据队列中优先值的大小来实现的。优先级最高的元素将被第一个执行，而不是像队列FIFO和栈LIFO里面的完全根据最先进入或者最后进入的顺序进行操作。有了优先级的概念，如果按照优先级将所有元素进行排序后进行操作则对操作的时间和空间复杂度要求过高，完全没必要。所有优先队列的实现借助了完全二叉树和列表两种数据结构的特定，并根据自身的需求提出了二叉堆这一更加简洁的数据结构，基于二叉堆，优先队列的实现将更加容易，本例中将优先级整数数值来衡量元素的优先值大小。

# 优先队列-->二叉堆
​
​
class SQ(object):
    """优先队列，二叉堆"""
    def __init__(self):
        self.list = []
​
    def getMax(self):
        # 根节点为最大树
        return self.list[0]
​
    def delMax(self):
        # 删除值最大的节点
        self.list[0] = self.list.pop()
        j = len(self.list) - 1
        i = 0
        # 下滤
        while (i+1)*2 <= j and i*2+1 <= j:
            if self.list[i*2+1] > self.list[(i+1)*2]:
                if self.list[i] < self.list[i*2+1]:
                    self.list[i], self.list[i*2+1] = self.list[i*2+1], self.list[i]
                    i = i*2+1
                else:
                    return
            else:
                if self.list[i] < self.list[(i+1)*2]:
                    self.list[i], self.list[(i+1)*2] = self.list[(i+1)*2], self.list[i]
                    i = (i+1)*2
                else:
                    return
        # 退出循环后还有左儿子处在最后一个节点未比较的情况
        if i*2+1 == j and self.list[i] < self.list[i*2+1]:
            self.list[i], self.list[i*2+1] = self.list[i*2+1], self.list[i]
​
    def insert(self, elem):
        self.list.append(elem)
        i = len(self.list) - 1
        # 上滤
        while self.list[i] > self.list[int((i-1)/2)] and i != 0:
            self.list[i], self.list[int((i-1)/2)] = self.list[int((i-1)/2)], self.list[i]
            i = int((i-1)/2)
​
    def delMin(self):
        # 删除值最小的节点
        leaf = []
        i = len(self.list) - 1
        # 在所有叶子中寻找最小节点
        while i*2+1 > i:
            leaf.append(self.list.pop(i))
            i -= 1
        leaf.remove(min(leaf))
        while leaf:
            self.insert(leaf.pop())
​
​
if __name__ == "__main__":
    sq = SQ()
    sq.insert(3)
    sq.insert(6)
    sq.insert(7)
    sq.insert(4)
    sq.insert(2)
    sq.insert(1)
    sq.insert(23)
    sq.insert(9)
    print(sq.list)
    sq.delMax()
    print(sq.list)
    sq.delMin()
    print(sq.list)
    sq.delMin()
    print(sq.list)
​