05_Priority Queues 优先队列

title: 05_Priority Queues 优先队列
categories: 02_Silver
tags:

• 优先队列
• 堆
• Priority Queue
• Heap

Priority Queues 优先队列

简介

优先队列（Priority Queue 或 Heap）支持以下操作：

• 插入元素
• 删除最高优先级元素
• 获取最高优先级元素

以上操作的时间复杂度均为O(log N)。

优先队列比集合更简单更快，应尽可能使用优先队列。

Python 实现

注意：Python（与 C++ 不同）中删除和获取的是最小元素。

heapq不是封装好的类，而是直接操作传入的列表，将其转换为堆。

警告：由于堆的结构特性，打印 pq 不会按排序顺序打印元素，而是直接打印列表。

基本操作

importheapq pq=[]# 对于长度大于1的列表，需要用 heapify 转换为堆heapq.heapify(pq)heapq.heappush(pq,7)# [7]heapq.heappush(pq,2)# [7, 2]heapq.heappush(pq,1)# [7, 2, 1]heapq.heappush(pq,5)# [7, 5, 2, 1]print(pq[0])# 1 （获取最小元素）heapq.heappop(pq)# 弹出最小值 [7, 5, 2]heapq.heappop(pq)# 弹出最小值 [7, 5]heapq.heappush(pq,6)# [7, 6, 5]

常用方法

大顶堆

Python 的 heapq 只支持小顶堆。要实现大顶堆，可以取负值：

# 大顶堆heapq.heappush(heap,-x)# 存入负值-x=-heapq.heappop(heap)# 取出时取负

例题：Room Allocation

CSES - Room Allocation

问题描述

给定 n 个客户的到达和离开时间，求所需的最少房间数。

思路

1. 按到达时间排序所有客户
2. 维护一个小顶堆，存储已处理客户的离开时间
3. 对于每个客户：
   • 如果堆顶的离开时间 < 新客户的到达时间，说明有房间空出，弹出堆顶并放入新客户的离开时间
   • 否则，所有房间都满了，需要分配新房间

代码

importheapqimportsys n=int(sys.stdin.readline())timetable=[]forcustomerinrange(n):arrival,departure=map(int,sys.stdin.readline().split())timetable.append((arrival,departure,customer))timetable.sort(key=lambdax:x[0])# 按到达时间排序priority_queue=[]# 存储 (离开时间, 客户编号)room_numbers=[-1]*n# 房间分配结果forarrival,departure,customerintimetable:ifpriority_queueandarrival>priority_queue[0][0]:# 有空房间room_numbers[customer]=room_numbers[priority_queue[0][1]]heapq.heapreplace(priority_queue,(departure,customer))else:# 需要新房间heapq.heappush(priority_queue,(departure,customer))room_numbers[customer]=len(priority_queue)print(len(priority_queue))print(*room_numbers)

复杂度

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

更多例题

思路总结

优先队列常用于：

1. 贪心算法：每次选择最小/最大的元素
2. 多路归并：合并多个有序序列
3. 求 Top K：维护最大的 K 个元素
4. 任务调度：按优先级处理任务
5. 滑动窗口：维护窗口内的最值