优先队列
概述
优先队列（Priority Queue）是一种特殊的队列数据结构，其中每个元素都有一个**优先级**。出队操作总是返回优先级最高（或最低）的元素，而不是按照"先进先出"的原则。
核心特征： 优先队列的出队顺序由元素的优先级决定，而非入队顺序。通常使用堆（Heap） 来实现，保证高效的插入和删除操作。
与普通队列的对比
Text Only
优先队列特点
1. 优先级出队
元素按照优先级顺序出队，而非入队顺序：
大根堆 ：优先级高的元素先出（最大值优先）小根堆 ：优先级低的元素先出（最小值优先）
Text Only
2. 动态维护
优先队列支持动态插入和删除，始终维护堆的性质：
flowchart LR
A[初始堆] --> B[插入新元素]
B --> C[上浮调整]
C --> D[恢复堆性质]
D --> E[删除堆顶]
E --> F[下沉调整]
F --> G[恢复堆性质]3. 堆实现
优先队列通常使用**二叉堆**实现，二叉堆是一棵完全二叉树：
Text Only
4. 高效操作
操作
时间复杂度
说明
插入
O(log n)
添加到末尾后上浮
删除最值
O(log n)
交换后下沉
获取最值
O(1)
直接访问堆顶
建堆
O(n)
从下往上依次下沉
原理详解
二叉堆的数组表示
二叉堆使用数组存储，利用完全二叉树的性质：
Text Only
堆的性质
Text Only
上浮操作（Swim）
当插入新元素或增大某元素的值时，需要上浮以恢复堆性质：
Text Only
下沉操作（Sink）
当删除堆顶或减小某元素的值时，需要下沉以恢复堆性质：
Text Only
建堆过程
从无序数组构建堆，有两种方法：
Text Only
可视化演示
插入操作流程
sequenceDiagram
participant PQ as 优先队列
participant Array as 数组
participant Heap as 堆结构
Note over PQ: 初始状态: [10, 9, 8, 7]
PQ->>Array: push(12)
Array->>Array: data[++size] = 12
Note over Array: 数组: [10, 9, 8, 7, 12]
Note over Heap: 开始上浮调整
Heap->>Heap: 比较 12 与父节点 9
Note over Heap: 12 > 9，交换
Note over Array: 数组: [10, 12, 8, 7, 9]
Heap->>Heap: 比较 12 与父节点 10
Note over Heap: 12 > 10，交换
Note over Array: 数组: [12, 10, 8, 7, 9]
Note over PQ: 插入完成，堆顶为 12删除操作流程
sequenceDiagram
participant PQ as 优先队列
participant Array as 数组
participant Heap as 堆结构
Note over PQ: 当前状态: [12, 10, 8, 7, 9]
PQ->>Array: pop() 返回堆顶 12
Array->>Array: data[1] = data[size--]
Note over Array: 数组: [9, 10, 8, 7]
Note over Heap: 开始下沉调整
Heap->>Heap: 比较 9 与子节点 10, 8
Note over Heap: 较大子节点是 10，9 < 10，交换
Note over Array: 数组: [10, 9, 8, 7]
Note over Heap: 检查 9 的子节点（无）
Note over PQ: 删除完成，堆顶为 10大根堆完整操作演示
Text Only
代码实现
数组实现（大根堆）
C C++ Python Java Go Rust
C typedef struct {
int * data ; // 数据数组（从索引1开始存储）
int size ; // 当前元素数量
int capacity ; // 容量
} PriorityQueue ;
// 创建优先队列
PriorityQueue * createPQ ( int capacity ) {
PriorityQueue * pq = ( PriorityQueue * ) malloc ( sizeof ( PriorityQueue ));
pq -> data = ( int * ) malloc ( sizeof ( int ) * ( capacity + 1 )); // 索引0不使用
pq -> size = 0 ;
pq -> capacity = capacity ;
return pq ;
}
// 交换两个元素
void swap ( int * a , int * b ) {
int temp = * a ;
* a = * b ;
* b = temp ;
}
// 上浮操作（大根堆）
void swim ( int * data , int index ) {
// 当当前节点大于父节点时，向上交换
while ( index > 1 && data [ index / 2 ] < data [ index ]) {
swap ( & data [ index / 2 ], & data [ index ]);
index = index / 2 ; // 移动到父节点位置
}
}
// 下沉操作（大根堆）
void sink ( int * data , int size , int index ) {
// 当有子节点时
while ( 2 * index <= size ) {
int j = 2 * index ; // 左子节点
// 选择较大的子节点
if ( j < size && data [ j ] < data [ j + 1 ]) j ++ ;
// 如果当前节点已经大于等于子节点，停止
if ( data [ index ] >= data [ j ]) break ;
// 交换并继续下沉
swap ( & data [ index ], & data [ j ]);
index = j ;
}
}
// 插入元素
void push ( PriorityQueue * pq , int value ) {
if ( pq -> size >= pq -> capacity ) return ;
pq -> data [ ++ pq -> size ] = value ; // 添加到末尾
swim ( pq -> data , pq -> size ); // 上浮调整
}
// 获取堆顶元素
int top ( PriorityQueue * pq ) {
if ( pq -> size == 0 ) return -1 ;
return pq -> data [ 1 ];
}
// 删除并返回堆顶元素
int pop ( PriorityQueue * pq ) {
if ( pq -> size == 0 ) return -1 ;
int max = pq -> data [ 1 ]; // 保存堆顶
pq -> data [ 1 ] = pq -> data [ pq -> size -- ]; // 将末尾元素移到堆顶
sink ( pq -> data , pq -> size , 1 ); // 下沉调整
return max ;
}
// 判空
int isEmpty ( PriorityQueue * pq ) {
return pq -> size == 0 ;
}
C++ #include <vector>
#include <algorithm>
template < typename T , typename Compare = std :: less < T >>
class PriorityQueue {
private :
std :: vector < T > data ; // 从索引0开始
Compare comp ; // 比较器
// 上浮操作
void swim ( int index ) {
while ( index > 0 ) {
int parent = ( index - 1 ) / 2 ;
if ( comp ( data [ parent ], data [ index ])) {
std :: swap ( data [ parent ], data [ index ]);
index = parent ;
} else {
break ;
}
}
}
// 下沉操作
void sink ( int index ) {
int n = data . size ();
while ( 2 * index + 1 < n ) {
int left = 2 * index + 1 ;
int right = 2 * index + 2 ;
int target = index ;
// 选择优先级更高的子节点
if ( left < n && comp ( data [ target ], data [ left ])) {
target = left ;
}
if ( right < n && comp ( data [ target ], data [ right ])) {
target = right ;
}
if ( target == index ) break ;
std :: swap ( data [ index ], data [ target ]);
index = target ;
}
}
public :
PriorityQueue () = default ;
void push ( const T & value ) {
data . push_back ( value );
swim ( data . size () - 1 );
}
void pop () {
if ( data . empty ()) return ;
data [ 0 ] = data . back ();
data . pop_back ();
if ( ! data . empty ()) sink ( 0 );
}
T top () const { return data . front (); }
bool empty () const { return data . empty (); }
size_t size () const { return data . size (); }
};
// STL使用示例
#include <queue>
void demonstratePriorityQueue () {
// 大根堆（默认）
std :: priority_queue < int > maxPQ ;
maxPQ . push ( 3 );
maxPQ . push ( 1 );
maxPQ . push ( 4 );
// 小根堆（使用 std::greater）
std :: priority_queue < int , std :: vector < int > , std :: greater < int >> minPQ ;
minPQ . push ( 3 );
minPQ . push ( 1 );
minPQ . push ( 4 );
}
Python import heapq
# 使用内置heapq（小根堆）
min_heap = []
heapq . heappush ( min_heap , 3 )
heapq . heappush ( min_heap , 1 )
heapq . heappush ( min_heap , 4 )
# 弹出最小值
print ( heapq . heappop ( min_heap )) # 输出: 1
# 大根堆实现（取负值）
max_heap = []
heapq . heappush ( max_heap , - 3 )
heapq . heappush ( max_heap , - 1 )
heapq . heappush ( max_heap , - 4 )
print ( - heapq . heappop ( max_heap )) # 输出: 4
# 完整实现
class PriorityQueue :
def __init__ ( self , is_min_heap = True ):
self . data = []
self . is_min_heap = is_min_heap
def push ( self , value ):
if self . is_min_heap :
heapq . heappush ( self . data , value )
else :
heapq . heappush ( self . data , - value )
def pop ( self ):
if not self . data :
return None
if self . is_min_heap :
return heapq . heappop ( self . data )
else :
return - heapq . heappop ( self . data )
def top ( self ):
if not self . data :
return None
return self . data [ 0 ] if self . is_min_heap else - self . data [ 0 ]
def empty ( self ):
return len ( self . data ) == 0
def size ( self ):
return len ( self . data )
Java import java.util.PriorityQueue ;
import java.util.Collections ;
// 使用内置PriorityQueue（小根堆）
PriorityQueue < Integer > minPQ = new PriorityQueue <> ();
minPQ . offer ( 3 );
minPQ . offer ( 1 );
minPQ . offer ( 4 );
// 弹出最小值
System . out . println ( minPQ . poll ()); // 输出: 1
// 大根堆
PriorityQueue < Integer > maxPQ = new PriorityQueue <> ( Collections . reverseOrder ());
maxPQ . offer ( 3 );
maxPQ . offer ( 1 );
maxPQ . offer ( 4 );
System . out . println ( maxPQ . poll ()); // 输出: 4
// 数组实现版本
class BinaryHeap {
private int [] data ;
private int size ;
private int capacity ;
public BinaryHeap ( int capacity ) {
this . data = new int [ capacity + 1 ] ; // 索引0不使用
this . size = 0 ;
this . capacity = capacity ;
}
private void swim ( int index ) {
while ( index > 1 && data [ index / 2 ] < data [ index ] ) {
int temp = data [ index / 2 ] ;
data [ index / 2 ] = data [ index ] ;
data [ index ] = temp ;
index = index / 2 ;
}
}
private void sink ( int index ) {
while ( 2 * index <= size ) {
int j = 2 * index ;
if ( j < size && data [ j ] < data [ j + 1 ] ) j ++ ;
if ( data [ index ] >= data [ j ] ) break ;
int temp = data [ index ] ;
data [ index ] = data [ j ] ;
data [ j ] = temp ;
index = j ;
}
}
public void push ( int value ) {
data [++ size ] = value ;
swim ( size );
}
public int pop () {
int max = data [ 1 ] ;
data [ 1 ] = data [ size --] ;
sink ( 1 );
return max ;
}
public int top () {
return data [ 1 ] ;
}
public boolean isEmpty () {
return size == 0 ;
}
}
Go package main
import "container/heap"
// 使用内置heap接口
type MinHeap [] int
func ( h MinHeap ) Len () int { return len ( h ) }
func ( h MinHeap ) Less ( i , j int ) bool { return h [ i ] < h [ j ] }
func ( h MinHeap ) Swap ( i , j int ) { h [ i ], h [ j ] = h [ j ], h [ i ] }
func ( h * MinHeap ) Push ( x interface {}) { * h = append ( * h , x .( int )) }
func ( h * MinHeap ) Pop () interface {} {
old := * h
n := len ( old )
x := old [ n - 1 ]
* h = old [ 0 : n - 1 ]
return x
}
// 数组实现版本
type PriorityQueue struct {
data [] int
size int
capacity int
}
func NewPQ ( capacity int ) * PriorityQueue {
return & PriorityQueue {
data : make ([] int , capacity + 1 ),
size : 0 ,
capacity : capacity ,
}
}
func ( pq * PriorityQueue ) swim ( index int ) {
for index > 1 && pq . data [ index / 2 ] < pq . data [ index ] {
pq . data [ index / 2 ], pq . data [ index ] = pq . data [ index ], pq . data [ index / 2 ]
index = index / 2
}
}
func ( pq * PriorityQueue ) sink ( index int ) {
for 2 * index <= pq . size {
j := 2 * index
if j < pq . size && pq . data [ j ] < pq . data [ j + 1 ] {
j ++
}
if pq . data [ index ] >= pq . data [ j ] {
break
}
pq . data [ index ], pq . data [ j ] = pq . data [ j ], pq . data [ index ]
index = j
}
}
func ( pq * PriorityQueue ) Push ( value int ) {
pq . size ++
pq . data [ pq . size ] = value
pq . swim ( pq . size )
}
func ( pq * PriorityQueue ) Pop () int {
max := pq . data [ 1 ]
pq . data [ 1 ] = pq . data [ pq . size ]
pq . size --
pq . sink ( 1 )
return max
}
func ( pq * PriorityQueue ) Top () int {
return pq . data [ 1 ]
}
func ( pq * PriorityQueue ) Empty () bool {
return pq . size == 0
}
Rust use std :: collections :: BinaryHeap ;
// 使用内置BinaryHeap（大根堆）
let mut max_heap : BinaryHeap < i32 > = BinaryHeap :: new ();
max_heap . push ( 3 );
max_heap . push ( 1 );
max_heap . push ( 4 );
// 弹出最大值
println! ( "{:?}" , max_heap . pop ()); // 输出: Some(4)
// 小根堆（使用Reverse）
use std :: cmp :: Reverse ;
let mut min_heap : BinaryHeap < Reverse < i32 >> = BinaryHeap :: new ();
min_heap . push ( Reverse ( 3 ));
min_heap . push ( Reverse ( 1 ));
min_heap . push ( Reverse ( 4 ));
// 数组实现版本
struct PriorityQueue {
data : Vec < i32 > ,
}
impl PriorityQueue {
fn new ( capacity : usize ) -> Self {
let mut data = Vec :: with_capacity ( capacity + 1 );
data . push ( 0 ); // 索引0不使用
PriorityQueue { data }
}
fn swim ( & mut self , mut index : usize ) {
while index > 1 && self . data [ index / 2 ] < self . data [ index ] {
self . data . swap ( index / 2 , index );
index = index / 2 ;
}
}
fn sink ( & mut self , mut index : usize ) {
let size = self . data . len () - 1 ;
while 2 * index <= size {
let mut j = 2 * index ;
if j < size && self . data [ j ] < self . data [ j + 1 ] {
j += 1 ;
}
if self . data [ index ] >= self . data [ j ] {
break ;
}
self . data . swap ( index , j );
index = j ;
}
}
fn push ( & mut self , value : i32 ) {
self . data . push ( value );
self . swim ( self . data . len () - 1 );
}
fn pop ( & mut self ) -> Option < i32 > {
if self . data . len () <= 1 {
return None ;
}
let max = self . data [ 1 ];
let last = self . data . pop (). unwrap ();
if self . data . len () > 1 {
self . data [ 1 ] = last ;
self . sink ( 1 );
}
Some ( max )
}
fn top ( & self ) -> Option < i32 > {
if self . data . len () <= 1 {
None
} else {
Some ( self . data [ 1 ])
}
}
fn is_empty ( & self ) -> bool {
self . data . len () <= 1
}
}
复杂度分析
时间复杂度
操作
时间复杂度
说明
插入 push
O(log n)
最多上浮树高次
删除堆顶 pop
O(log n)
最多下沉树高次
获取堆顶 top
O(1)
直接访问 data[1]
建堆 buildHeap
O(n)
从下往上依次下沉
建堆复杂度推导
Text Only
空间复杂度
数组实现 : O(n)，存储所有元素链式实现 : O(n)，存储节点和指针
应用场景
1. 合并K个有序链表
使用小根堆维护K个链表的当前节点：
C typedef struct ListNode {
int val ;
struct ListNode * next ;
} ListNode ;
typedef struct {
int val ; // 节点值
int listIndex ; // 来自哪个链表
} HeapNode ;
ListNode * mergeKLists ( ListNode ** lists , int k ) {
MinPQ * pq = createMinPQ ( k );
// 将各链表头节点入堆
for ( int i = 0 ; i < k ; i ++ ) {
if ( lists [ i ]) {
pushMin ( pq , lists [ i ] -> val );
}
}
ListNode dummy = { 0 , NULL };
ListNode * tail = & dummy ;
while ( ! isEmpty ( pq )) {
tail -> next = ( ListNode * ) malloc ( sizeof ( ListNode ));
tail -> next -> val = popMin ( pq );
tail -> next -> next = NULL ;
tail = tail -> next ;
}
return dummy . next ;
}
算法图解：
Text Only
2. Top K 问题
找出数组中出现频率最高的K个元素：
C int * topKFrequent ( int nums [], int n , int k , int * returnSize ) {
// 统计频率
int freq [ 10000 ] = { 0 };
for ( int i = 0 ; i < n ; i ++ ) {
freq [ nums [ i ] + 5000 ] ++ ;
}
// 使用小根堆维护Top K
MinPQ * pq = createMinPQ ( k + 1 );
int * result = ( int * ) malloc ( sizeof ( int ) * k );
* returnSize = 0 ;
for ( int i = 0 ; i < 10000 ; i ++ ) {
if ( freq [ i ] > 0 ) {
pushMin ( pq , freq [ i ]);
// 保持堆大小为K
if ( pq -> size > k ) {
popMin ( pq );
}
}
}
while ( ! isEmpty ( pq )) {
result [( * returnSize ) ++ ] = popMin ( pq );
}
return result ;
}
算法思路：
Text Only
3. 任务调度
优先级调度算法：
C typedef struct {
int id ; // 任务ID
int priority ; // 优先级
int arrival ; // 到达时间
int burst ; // 执行时间
} Task ;
void scheduleTasks ( Task tasks [], int n ) {
PriorityQueue * pq = createPQ ( n );
int time = 0 ;
int completed = 0 ;
while ( completed < n ) {
// 将已到达的任务加入队列
for ( int i = 0 ; i < n ; i ++ ) {
if ( tasks [ i ]. arrival <= time && tasks [ i ]. burst > 0 ) {
push ( pq , tasks [ i ]. priority );
}
}
// 执行优先级最高的任务
if ( ! isEmpty ( pq )) {
int priority = pop ( pq );
printf ( "Time %d: Execute task with priority %d \n " , time , priority );
completed ++ ;
}
time ++ ;
}
}
调度示例：
Text Only
4. Dijkstra 最短路径
使用优先队列优化Dijkstra算法：
flowchart LR
A[起点入堆<br/>dist=0] --> B[取出最小距离节点]
B --> C[更新邻接节点距离]
C --> D{堆是否为空?}
D -->|否| B
D -->|是| E[算法结束]5. Huffman 编码
构建最优前缀编码树：
Text Only
参考资料