优先队列(priority queue)详解

优先队列是一种特殊的队列数据结构，其中每个元素都有与之关联的"优先级"。与普通队列(FIFO)不同，优先队列中的元素按照优先级顺序出队，而不是按照插入顺序。

基本特性

1. 不是严格的FIFO：优先级最高的元素最先出队
2. 动态排序：当新元素加入时，队列会自动调整顺序
3. 主要操作：
   • insert/push：添加元素
   • deleteMin/deleteMax/pop：移除最高(或最低)优先级元素
   • peek：查看但不移除最高优先级元素

实现方式

优先队列通常可以通过以下数据结构实现：

1. 数组/链表(简单但低效)：

   • 无序数组/链表：插入O(1)，删除O(n)
   • 有序数组/链表：插入O(n)，删除O(1)

2. 二叉堆(最常用)：

   • 插入和删除都是O(log n)
   • 查找最高优先级元素O(1)

3. 平衡二叉搜索树：

   • 所有操作O(log n)
   • 但实现比堆复杂

示例代码(Python)

Python的heapq模块提供了优先队列实现(最小堆)：

import heapq
# 创建优先队列(最小堆)
pq = []
heapq.heapify(pq)
# 添加元素
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)
heapq.heappush(pq, 1)
# 查看并移除最小元素
print(heapq.heappop(pq))  # 输出1
print(heapq.heappop(pq))  # 输出2
print(heapq.heappop(pq))  # 输出5
print(heapq.heappop(pq))  # 输出8

实际应用示例

1. 医院急诊系统

import heapq

class Patient:
    def __init__(self, name, severity):
        self.name = name
        self.severity = severity  # 1-5，1为最严重
    
    def __lt__(self, other):
        return self.severity < other.severity

er_queue = []
heapq.heapify(er_queue)

# 病人到达
heapq.heappush(er_queue, Patient("John", 3))
heapq.heappush(er_queue, Patient("Mary", 1))  # 最紧急
heapq.heappush(er_queue, Patient("Bob", 4))

# 处理病人
next_patient = heapq.heappop(er_queue)
print(f"正在治疗: {next_patient.name} (紧急程度 {next_patient.severity})")
# 输出: 正在治疗: Mary (紧急程度 1)

2. 任务调度系统

import heapq
from datetime import datetime

class Task:
    def __init__(self, description, priority, due_date):
        self.description = description
        self.priority = priority  # 1-10，10为最高
        self.due_date = due_date  # 截止日期
    
    def __lt__(self, other):
        # 先按优先级，再按截止日期
        if self.priority == other.priority:
            return self.due_date < other.due_date
        return self.priority > other.priority  # 注意：堆是最小堆，我们取反实现最大堆

tasks = []
heapq.heapify(tasks)
# 添加任务
heapq.heappush(tasks, Task("写报告", 5, datetime(2023, 12, 1)))
heapq.heappush(tasks, Task("修复紧急bug", 9, datetime(2023, 11, 15))))
heapq.heappush(tasks, Task("准备会议", 7, datetime(2023, 11, 20))))
# 处理任务
while tasks:
    next_task = heapq.heappop(tasks)
    print(f"处理任务: {next_task.description} (优先级: {next_task.priority}, 截止: {next_task.due_date.date()})")

输出:

处理任务: 修复紧急bug (优先级: 9, 截止: 2023-11-15)
处理任务: 准备会议 (优先级: 7, 截止: 2023-11-20)
处理任务: 写报告 (优先级: 5, 截止: 2023-12-01)

3. 合并K个有序链表(LeetCode问题)

import heapq

def merge_k_lists(lists):
    min_heap = []
    # 将每个链表的第一个元素推入堆
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(min_heap, (lst.val, i))
    
    dummy = ListNode(0)
    current = dummy
    
    while min_heap:
        val, i = heapq.heappop(min_heap)
        current.next = ListNode(val)
        current = current.next
        
        # 从取出元素的链表中取下一个元素
        if lists[i].next:
            lists[i] = lists[i].next
            heapq.heappush(min_heap, (lists[i].val, i))
    
    return dummy.next

复杂度分析

操作	无序数组	有序数组	二叉堆	平衡BST
插入(insert)	O(1)	O(n)	O(log n)	O(log n)
删除(delete)	O(n)	O(1)	O(log n)	O(log n)
查找最小/最大	O(n)	O(1)	O(1)	O(log n)

变体

1. 双端优先队列：支持高效查找和删除最小和最大元素
2. 最大-最小堆：同时支持高效查找最小和最大元素
3. 斐波那契堆：某些操作比二叉堆更高效，但实现复杂

优先队列是许多算法(如Dijkstra最短路径算法、Prim最小生成树算法、Huffman编码等)的核心数据结构，理解其原理和实现对于算法学习非常重要。