优先队列详解：数据结构中的「VIP通道」

掌握优先队列，轻松解决 Top K 和动态数据流问题

什么是优先队列

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个「优先级」，出队时总是优先级最高的元素先出队。

核心特点：不是先进先出（FIFO），而是按优先级出队

形象理解

想象你在机场登机：

1
2
普通队列：先到先登机
优先队列：VIP/头等舱先登机，然后才是经济舱

底层实现：堆（Heap）

优先队列通常用堆来实现：

graph TD
    subgraph 最大堆
        A[9] --> B[7]
        A --> C[8]
        B --> D[3]
        B --> E[5]
        C --> F[6]
        C --> G[2]
    end
    
    style A fill:#FF6B6B
操作 时间复杂度 说明
插入 O(log n) 上浮调整
取出堆顶 O(log n) 下沉调整
查看堆顶 O(1) 不需要调整
建堆 O(n) 从下往上调整

C++ 中的优先队列

基本语法

1
2
3
4
5
6
7
#include <queue>

// 最大堆（默认）
priority_queue<int> maxHeap;

// 最小堆
priority_queue<int, vector<int>, greater<int>> minHeap;

常用操作

1
2
3
4
5
6
7
priority_queue<int> pq;

pq.push(5);     // 插入元素
pq.top();       // 查看堆顶（不删除）
pq.pop();       // 删除堆顶
pq.empty();     // 是否为空
pq.size();      // 元素个数

自定义比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 方法1：使用 lambda
auto cmp = [](int a, int b) { return a > b; };  // 最小堆
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

// 方法2：存储 pair
auto cmp = [](pair<int,int>& a, pair<int,int>& b) {
    return a.second > b.second;  // 按 second 的最小堆
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

// 方法3：自定义结构体
struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // 最小堆
    }
};
priority_queue<int, vector<int>, Compare> pq;

注意：C++ 优先队列的比较器与 sort 相反！return a > b 表示最小堆

典型应用场景

graph LR
    A[优先队列] --> B[Top K 问题]
    A --> C[合并 K 个有序结构]
    A --> D[数据流统计]
    A --> E[贪心算法]
    A --> F[堆排序]
    
    B --> B1[第K大元素]
    B --> B2[前K个高频元素]
    
    C --> C1[合并K个链表]
    C --> C2[合并K个数组]
    
    D --> D1[数据流中位数]
    D --> D2[滑动窗口最大值]
    
    style A fill:#FFE4B5
    style B fill:#87CEEB
    style C fill:#90EE90
    style D fill:#DDA0DD

经典问题详解

1. 数组中的第K个最大元素

LeetCode 215: 在未排序的数组中找到第 k 个最大的元素

问题分析

1
2
3
4
5
输入：[3, 2, 1, 5, 6, 4], k = 2
输出：5

排序后：[1, 2, 3, 4, 5, 6]
第2大：5

解法选择

方法 时间复杂度 空间复杂度 适用场景
排序 O(n log n) O(1) 简单直接
最小堆 O(n log k) O(k) k 远小于 n
快速选择 O(n) 平均 O(1) 一次性查询

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findKthLargest(vector<int>& nums, int k) {
    // 最小堆
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        // 保持堆大小为 k
        if (minHeap.size() > k) {
            minHeap.pop();  // 移除最小的
        }
    }
    
    return minHeap.top();  // 堆顶就是第 k 大
}

原理图解

1
2
3
4
5
6
7
8
9
10
11
k = 2
数组：[3, 2, 1, 5, 6, 4]

step 1: push 3 → [3]
step 2: push 2 → [2, 3]
step 3: push 1 → [1, 2, 3] → pop → [2, 3]
step 4: push 5 → [2, 3, 5] → pop → [3, 5]
step 5: push 6 → [3, 5, 6] → pop → [5, 6]
step 6: push 4 → [4, 5, 6] → pop → [5, 6]

堆顶 = 5 = 第2大

2. 前K个高频元素

LeetCode 347: 给定一个非空的整数数组，返回其中出现频率前 k 高的元素

问题分析

1
2
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1, 2]

两步走策略

graph LR
    A[统计频率] --> B[维护 Top K]
    
    A --> A1["哈希表 O(n)"]
    B --> B1["最小堆 O(n log k)"]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<int> topKFrequent(vector<int>& nums, int k) {
    // Step 1: 统计频率
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    
    // Step 2: 最小堆维护 Top K
    auto cmp = [](pair<int, int>& a, pair<int, int>& b) {
        return a.second > b.second;  // 按频率，小的在堆顶
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> minHeap(cmp);
    
    for (auto& [num, count] : freq) {
        minHeap.push({num, count});
        if (minHeap.size() > k) {
            minHeap.pop();  // 移除频率最低的
        }
    }
    
    // Step 3: 收集结果
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    
    return result;
}

3. 合并K个升序链表

LeetCode 23: 给你一个链表数组，每个链表都已经按升序排列，请将所有链表合并到一个升序链表中

问题分析

1
2
输入：[[1,4,5], [1,3,4], [2,6]]
输出：[1,1,2,3,4,4,5,6]

解法对比

方法 时间复杂度 说明
逐一合并 O(kn) 简单但慢
分治合并 O(n log k) 类似归并排序
优先队列 O(n log k) 每次取最小

代码实现（数组模拟）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<int> mergeKSortedArrays(vector<vector<int>>& arrays) {
    vector<int> result;
    
    // 最小堆：{值, 数组索引, 元素索引}
    auto cmp = [](auto& a, auto& b) {
        return get<0>(a) > get<0>(b);
    };
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> minHeap(cmp);
    
    // 初始化：加入每个数组的第一个元素
    for (int i = 0; i < arrays.size(); ++i) {
        if (!arrays[i].empty()) {
            minHeap.push({arrays[i][0], i, 0});
        }
    }
    
    while (!minHeap.empty()) {
        auto [val, arrIdx, elemIdx] = minHeap.top();
        minHeap.pop();
        result.push_back(val);
        
        // 加入该数组的下一个元素
        if (elemIdx + 1 < arrays[arrIdx].size()) {
            minHeap.push({arrays[arrIdx][elemIdx + 1], arrIdx, elemIdx + 1});
        }
    }
    
    return result;
}

过程图解

1
2
3
4
5
6
7
8
9
10
11
arrays: [[1,4,5], [1,3,4], [2,6]]

初始堆：[(1,0,0), (1,1,0), (2,2,0)]
        堆顶 = 1

Step 1: pop (1,0,0) → result=[1] → push (4,0,1)
Step 2: pop (1,1,0) → result=[1,1] → push (3,1,1)
Step 3: pop (2,2,0) → result=[1,1,2] → push (6,2,1)
...

最终：[1,1,2,3,4,4,5,6]

4. 数据流的中位数

LeetCode 295: 设计一个支持以下两种操作的数据结构：添加数字、返回中位数

核心思路：对顶堆

使用两个堆：

  • 最大堆：存储较小的一半
  • 最小堆：存储较大的一半
graph LR
    subgraph 较小的一半
        A[最大堆]
    end
    
    subgraph 较大的一半
        B[最小堆]
    end
    
    A -->|堆顶| C[中位数]
    B -->|堆顶| C
    
    style A fill:#87CEEB
    style B fill:#90EE90
    style C fill:#FFE4B5

核心约束

  1. 最大堆的所有元素 ≤ 最小堆的所有元素
  2. 两堆大小差不超过 1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MedianFinder {
private:
    priority_queue<int> maxHeap;  // 较小的一半
    priority_queue<int, vector<int>, greater<int>> minHeap;  // 较大的一半
    
public:
    void addNum(int num) {
        // Step 1: 先加入最大堆
        maxHeap.push(num);
        
        // Step 2: 最大堆的最大值移到最小堆
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        
        // Step 3: 平衡大小
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

插入过程演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
添加 [1, 2, 3]

add(1):
  maxHeap.push(1) → maxHeap: [1]
  move to minHeap → minHeap: [1]
  balance → maxHeap: [1], minHeap: []
  
add(2):
  maxHeap.push(2) → maxHeap: [2,1]
  move to minHeap → maxHeap: [1], minHeap: [2]
  (已平衡)

add(3):
  maxHeap.push(3) → maxHeap: [3,1]
  move to minHeap → maxHeap: [1], minHeap: [2,3]
  balance → maxHeap: [2,1], minHeap: [3]
  
中位数 = maxHeap.top() = 2

5. 最后一块石头的重量

LeetCode 1046: 每次选出最重的两块石头碰撞，返回最后剩下的石头重量

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> maxHeap(stones.begin(), stones.end());
    
    while (maxHeap.size() > 1) {
        int stone1 = maxHeap.top(); maxHeap.pop();
        int stone2 = maxHeap.top(); maxHeap.pop();
        
        if (stone1 != stone2) {
            maxHeap.push(stone1 - stone2);
        }
    }
    
    return maxHeap.empty() ? 0 : maxHeap.top();
}

6. K个最接近原点的点

LeetCode 973: 找出 K 个距离原点最近的点

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    // 最大堆：距离大的在堆顶
    auto cmp = [](pair<int,int>& a, pair<int,int>& b) {
        return a.first < b.first;
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> maxHeap(cmp);
    
    for (int i = 0; i < points.size(); ++i) {
        int dist = points[i][0]*points[i][0] + points[i][1]*points[i][1];
        maxHeap.push({dist, i});
        if (maxHeap.size() > k) {
            maxHeap.pop();  // 移除距离最大的
        }
    }
    
    vector<vector<int>> result;
    while (!maxHeap.empty()) {
        result.push_back(points[maxHeap.top().second]);
        maxHeap.pop();
    }
    return result;
}

7. 堆排序

利用堆的性质进行排序

算法步骤

  1. 建堆：将数组构建成最大堆
  2. 排序：依次将堆顶（最大值）与末尾交换，然后调整堆
graph TD
    subgraph 建堆
        A[无序数组] --> B[最大堆]
    end
    
    subgraph 排序
        B --> C[堆顶与末尾交换]
        C --> D[缩小堆范围]
        D --> E[调整堆]
        E -->|重复| C
    end
    
    E --> F[有序数组]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void heapSort(vector<int>& nums) {
    int n = nums.size();
    
    // 建堆：从最后一个非叶子节点开始
    for (int i = n/2 - 1; i >= 0; --i) {
        heapify(nums, n, i);
    }
    
    // 排序
    for (int i = n - 1; i > 0; --i) {
        swap(nums[0], nums[i]);  // 堆顶与末尾交换
        heapify(nums, i, 0);      // 调整堆
    }
}

void heapify(vector<int>& nums, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

复杂度分析

  • 时间：O(n log n)
  • 空间：O(1) 原地排序
  • 稳定性：不稳定

Top K 问题总结

选择合适的堆

问题 堆类型 原因
第 K 大元素 最小堆 堆顶是第 K 大
第 K 小元素 最大堆 堆顶是第 K 小
前 K 大元素 最小堆 淘汰堆顶（最小的）
前 K 小元素 最大堆 淘汰堆顶（最大的）

口诀

求大用小，求小用大

  • 求最大的 K 个 → 用最小堆
  • 求最小的 K 个 → 用最大堆

优先队列 vs 其他数据结构

数据结构 插入 删除堆顶 查找最值 任意查找
无序数组 O(1) O(n) O(n) O(n)
有序数组 O(n) O(1) O(1) O(log n)
优先队列 O(log n) O(log n) O(1) ❌
平衡树 O(log n) O(log n) O(log n) O(log n)

思维导图

graph TD
    A[优先队列] --> B[基础操作]
    A --> C[经典问题]
    A --> D[高级应用]
    
    B --> B1[push/pop/top]
    B --> B2[自定义比较器]
    B --> B3[最大堆/最小堆]
    
    C --> C1[Top K 问题]
    C --> C2[合并 K 个链表]
    C --> C3[数据流中位数]
    
    D --> D1[任务调度]
    D --> D2[Dijkstra 最短路]
    D --> D3[Huffman 编码]
    
    style A fill:#FFE4B5
    style C1 fill:#87CEEB
    style C2 fill:#90EE90
    style C3 fill:#DDA0DD

总结

核心要点

  1. 优先队列 = 堆：底层用堆实现，O(log n) 插入删除
  2. 求大用小：需要最大的 K 个，用最小堆
  3. 对顶堆：维护动态中位数的经典技巧
  4. 堆排序：O(n log n)，原地排序

常见模式

模式 典型问题 关键点
固定大小堆 第 K 大 堆大小保持 K
对顶堆 数据流中位数 两个堆，一大一小
多路归并 合并 K 个链表 每次取最小的那条
贪心 + 堆 任务调度 优先处理某种特性的任务

代码模板

1
2
3
4
5
6
7
8
9
10
11
// Top K 问题模板
priority_queue<int, vector<int>, greater<int>> minHeap;  // 最小堆

for (int num : nums) {
    minHeap.push(num);
    if (minHeap.size() > k) {
        minHeap.pop();
    }
}

// minHeap.top() 就是第 K 大

推荐阅读：