priority queue优先队列（三）

一、优先队列

优先队列不再遵循先进先出的原则，而是分为两种情况: ·

最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队。 ·
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队。

在操作系统中，我们常常会根据优先级来处理任务，比如系统的优先级最高，我们肯定优先处理系统任务，然后才处理用户的任务。

因此，可以用最大堆来实现最大优先队列，这样的话，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

class PriorityQueue:
    def __init__(self):
        '''初始化数组，大小'''
        self.array = []
        self.size = 0

    def enqueue(self, element):
        '''入队：堆的插入，添加到尾部'''
        self.array.append(element)
        self.size += 1
        # 上浮
        self.up_adjust()
        return self.array

    def dequeue(self):
        '''出队：是删除堆顶节点'''
        if self.size < 0:
            raise Exception("队列为空 !")
        head = self.array[0]
        self.array[0] = self.array[self.size - 1]
        self.size -= 1
        # 下沉
        self.down_adjust()
        # return head
        print(head,"出队")
        return self.array

    def up_adjust(self):
        '''上浮'''
        child_index = self.size - 1
        parent_index = (child_index - 1) // 2
        # temp保存插入的叶子节点值，用于最后的赋值
        temp = self.array[child_index]
        while child_index > 0 and temp > self.array[parent_index]:
            # 无需真正交换，单向赋值即可
            self.array[child_index] = self.array[parent_index]
            child_index = parent_index
            parent_index = (parent_index - 1) // 2
        self.array[child_index] = temp

    def down_adjust(self):
        '''下沉'''
        parent_index = 0
        # temp保存父节点值，用于最后的赋值
        temp = self.array[parent_index]
        child_index = 1
        while child_index < self.size:
            # 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if child_index + 1 < self.size and self.array[child_index + 1] > self.array[child_index]:
                child_index += 1
            # 如果父节点大于任何一个孩子的值，直接跳出
            if temp >= self.array[child_index]:
                break
            # 无需真正交换，单向赋值即可
            self.array[parent_index] = self.array[child_index]
            parent_index = child_index
            child_index = 2 * child_index + 1
        self.array[parent_index] = temp


if __name__ == '__main__':
    # 优先队列对象
    queue = PriorityQueue()
    # 入队
    print(queue.enqueue(30))
    print(queue.enqueue(50))
    print(queue.enqueue(10))
    print(queue.enqueue(20))
    print(queue.enqueue(80))
    # 出队
    print(queue.dequeue())
    print(queue.dequeue())