Python 数据结构基础（四）：优先队列

1. 优先队列的定义

优先队列（Priority Queue）是一种特殊的队列，它根据元素的优先级来决定元素的出队顺序。在优先队列中，优先级最高的元素会优先出队，而优先级最低的元素会最后出队。优先队列与普通队列最大的不同点在于 出队顺序。

普通队列的出队顺序跟入队顺序相关，符合 先进先出（First in, First out） 的规则。
优先队列的出队顺序跟入队顺序无关，优先队列是按照元素的优先级来决定出队顺序的。优先级高的元素优先出队，优先级低的元素后出队。优先队列符合 最高级先出（First in, Largest out） 的规则。

2. 优先队列的基本操作

优先队列和普通队列一样，都有入队（enqueue）和出队（dequeue）操作，但优先队列的出队操作需要根据元素的优先级来决定。优先队列的基本操作包括：

入队（enqueue）：将元素插入到优先队列中，根据元素的优先级来决定插入的位置。
出队（dequeue）：从优先队列中删除优先级最高的元素，并返回该元素。

优先队列的入队操作和出队操作的时间复杂度都是 O(log n)，其中 n 是优先队列中的元素数量。

3. 优先队列的实现方法

优先队列除了可以通过链表、数组等数据结构来实现外，还可以通过堆（Heap）来实现。堆是一种特殊的完全二叉树，它满足以下两个性质：

堆顶元素是最小（或最大）的元素： 堆顶元素是堆中的最小（或最大）元素，即堆顶元素的优先级最高（或最低）。
堆中每个节点的值都小于（或大于）其子节点的值： 堆中每个节点的值都小于（或大于）其子节点的值，即堆中每个节点的优先级都小于（或大于）其子节点的优先级。

Python 内置了 heapq 模块，可以用来实现优先队列。heapq 模块提供了两个函数：heappush 和 heappop，分别用于向优先队列中插入元素和删除优先级最高的元素。

注意 heapq 模块只创建了最小堆，如果要创建最大堆，可以在插入元素时将元素的优先级取负数。

import heapq

class PriorityQueue:
    def __init__(self):
        self.queue = []
        self.index = 0

    def is_empty(self):
        return len(self.queue) == 0

    def enqueue(self, item, priority):
        heapq.heappush(self.queue, (-priority, self.index, item))
        self.index += 1

    def dequeue(self):
        return heapq.heappop(self.queue)[-1]

4. 优先队列的应用场景

优先队列在计算机科学中有着广泛的应用，以下是一些常见的应用场景：

任务调度： 在任务调度中，优先队列可以用来决定任务的执行顺序。
最短路径算法： 在 Dijkstra 算法中，优先队列可以用来选择下一个要访问的节点。
数据压缩： 在 Huffman 编码中，优先队列可以用来选择出现频率最高的字符。
事件驱动编程： 在事件驱动编程中，优先队列可以用来处理事件，确保高优先级的事件先被处理。
负载均衡： 在负载均衡中，优先队列可以用来选择负载最低的服务器来处理请求。
实时系统： 在实时系统中，优先队列可以用来处理紧急任务，确保它们先被处理。
排序算法： 在排序算法中，利用优先队列来排序数据。

5. 优先队列的练习

5.1 滑动窗口最大值

描述： 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

要求： 返回 滑动窗口中的最大值 。

示例：

>>> nums = [1,3,-1,-3,5,3,6,7]
>>> k = 3
>>> slidingWindowMaximum(nums, k)
[3,3,5,5,6,7]

代码：

import heapq

def maxSlidingWindow_heap(nums: List[int], k: int) -> List[int]:
    # 边界条件
    if not nums or k == 0:
        return []
    
    # 初始化优先队列
    heap = []
    result = []

    for i in range(len(nums)):
        # 将元素加入优先队列
        heapq.heappush(heap, (-nums[i], i))

        # 移除堆顶元素
        while heap[0][1] <= i - k:
            heapq.heappop(heap)

        # 将堆顶元素加入结果
        if i >= k - 1:
            result.append(-heap[0][0])

    return result

5.2 前 K 个高频元素

描述： 给你一个整数数组 nums 和一个整数 k。

要求： 请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例：

>>> nums = [1,1,1,2,2,3]
>>> k = 2
>>> topKFrequent(nums, k)
[1,2]

代码：

import heapq
from collections import Counter

def topKFrequent(nums: List[int], k: int) -> List[int]:
    # 统计每个数字出现的频率
    frequency = Counter(nums)

    # 将频率和数字打包成元组，并放入优先队列
    heap = []
    for num, freq in frequency.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, num))
        elif freq > heap[0][0]:  # 比堆顶频率高
            heapq.heapreplace(heap, (freq, num))

    return [num for freq, num in heap]