一、优先队列
一种特殊的队列，在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先被删除。
- 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
