05_Priority Queues 优先队列

2026/8/16 8:34:51 拓冰建站浏览量

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]

常用方法

方法	说明
`heapq.heappush(pq, x)`	插入元素 x
`heapq.heappop(pq)`	弹出并返回最小值
`heapq.heapreplace(pq, x)`	弹出最小值并插入 x（原子操作）
`heapq.heapify(pq)`	将列表转换为堆

大顶堆

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

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

例题：Room Allocation

CSES - Room Allocation

问题描述

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

思路

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

代码

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)

建站实战干货