Python算法-优先队列（Priority Queue）

一、优先队列

一种特殊的队列，在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先被删除。

• 1、优先队列与普通队列的最大不同在于出队顺序
• 2、普通队列符合先进先出的规则
• 3、优先队列按照元素的优先级决定出队顺序，优先级高的元素先出队，优先级低的元素后出队。

二、优先队列的适用场景

• 数据压缩：赫夫曼编码算法；
• 最短路径算法：Dijkstra 算法；
• 最小生成树算法：Prim 算法；
• 任务调度器：根据优先级执行系统任务；
• 事件驱动仿真：顾客排队算法；
• 选择问题：查找第 k 个最小元素。

三、优先队列的实现方式

手写二叉堆实现优先队列

class Heapq:
    def heapAdjust(self, nums, index:int, end:int):
        left = index * 2 + 1
        right = left + 1
        while left <= end:
            # 当前节点为非叶子节点
            max_index = index
            if nums[left] > nums[max_index]:
                max_index = left
            if right < end and nums[right] > nums[max_index]:
                max_index = right
            if index == max_index:
                # 如果不用交换，则说明交换结束
                break
            # 更大的节点向上移动
            nums[index], nums[max_index] = nums[max_index], nums[index]
            # 继续调整子树
            index = max_index
            left = index * 2 + 1
            right = left + 1
    # 将数组构建为二叉堆
    def heapify(self, nums):
        size = len(nums)
        # (size - 2) // 2是最后一个非叶子节点，叶子节点不需要调整
        for i in range((size - 2)//2, -1, -1):
            # 调用调整堆函数
            self.heapAdjust(nums, i, size - 1)
    # 入队操作
    def heappush(self, nums:list, value):
        nums.append(value)
        size = len(nums)
        i = size - 1
        # 寻找插入位置
        while (i - 1) // 2 >= 0:
            cur_root = (i - 1)//2
            if nums[cur_root] > value:
                break
            # 继续向上查找哦
            nums[i] = nums[cur_root]
            i = cur_root
        # 找到插入位置或者到达根位置，将其插入
        nums[i] = value
    # 出队操作
    def heappop(self, nums:list):
        size = len(nums)
        nums[0], nums[-1] = nums[-1], nums[0]
        # 得到最大值（堆顶元素）然后调整堆
        top = nums.pop()
        if size > 0:
            self.heapAdjust(nums, 0, size - 2)
        return top
    # 升序堆排序
    def heapSort(self, nums):
        self.heapify(nums)
        size = len(nums)
        for i in range(size):
            nums[0], nums[size-i-1] = nums[size-i-1], nums[0]
            self.heapAdjust(nums, 0, size - i -2)
        return nums

使用heapq模块实现优先队列

import heapq

class PriorityQueue:
    def __init__(self):
        self.queue = []
        self.index = 0
    # 入队元素
    def push(self, item, priority):
        heapq.heappush(self.queue, (-priority, self.index, item))
        self.index += 1
    def pop(self):
        return heapq.heappop(self.queue)[-1]

239. 滑动窗口最大值

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        size = len(nums)
        # 将数组负数组成小堆顶，则堆顶元素的正数则为窗口内的最大值
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        res = [-q[0][0]]
        for i in range(k, size):
            heapq.heappush(q, (-nums[i], i))
            # 当二叉堆堆顶元素的索引已经不在滑动窗口的范围中时，
            # 即 q[0][1] <= i - k 时，不断删除堆顶元素，直到最大值元素的索引在滑动窗口的范围中。
            while q[0][1] <= i - k:
                heapq.heappop(q)
            res.append(-q[0][0])
        return res

内容参考：https://algo.itcharge.cn/04.%E9%98%9F%E5%88%97/03.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97/01.%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E7%9F%A5%E8%AF%86/