跳到主要内容

C++ priority_queue

什么是优先队列？​

优先队列(priority_queue)是STL容器适配器的一种，它提供了一种以特定顺序访问元素的方式。与普通队列(queue)不同，优先队列中的元素是按照优先级排序的，最高优先级的元素总是位于队列的前面。

特点概述
  • 顶部元素始终是优先级最高的
  • 插入或删除元素时会自动维护优先级顺序
  • 基于堆(heap)数据结构实现
  • 默认情况下使用std::less比较器，形成最大堆

基本操作​

优先队列定义在<queue>头文件中，下面是基本用法：

cpp
#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 创建一个优先队列，默认为最大堆
    priority_queue<int> pq;
    
    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);
    
    // 访问并弹出元素
    cout << "优先队列元素(从高到低)：";
    while (!pq.empty()) {
        cout << pq.top() << " "; // 输出最高优先级的元素
        pq.pop(); // 移除最高优先级的元素
    }
    
    return 0;
}

输出：

优先队列元素(从高到低)：30 20 10 5

常用成员函数​

优先队列提供了以下几个常用的成员函数：

  1. push(const value_type& val) - 插入元素并重新排序
  2. pop() - 移除顶部元素
  3. top() - 返回顶部元素（最高优先级的元素）
  4. size() - 返回元素个数
  5. empty() - 检查队列是否为空

自定义比较函数​

优先队列默认使用std::less比较器，形成最大堆（最大值优先）。如果需要最小堆或者自定义比较规则，可以自定义比较函数：

创建最小堆​

cpp
#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 创建一个最小堆的优先队列
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);
    minHeap.push(5);
    
    cout << "最小堆元素(从低到高)：";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    
    return 0;
}

输出：

最小堆元素(从低到高)：5 10 20 30

使用自定义比较函数​

如果需要根据复杂对象的某个属性进行排序，可以自定义比较函数：

cpp
#include <iostream>
#include <queue>
#include <string>
using namespace std;

// 学生类
struct Student {
    string name;
    int score;
    
    Student(string n, int s) : name(n), score(s) {}
};

// 自定义比较函数，按分数从高到低排序
struct CompareStudent {
    bool operator()(const Student& s1, const Student& s2) {
        // 注意：优先队列中"小于"表示优先级低
        return s1.score < s2.score;
    }
};

int main() {
    priority_queue<Student, vector<Student>, CompareStudent> studentPQ;
    
    studentPQ.push(Student("Alice", 85));
    studentPQ.push(Student("Bob", 92));
    studentPQ.push(Student("Charlie", 78));
    studentPQ.push(Student("David", 90));
    
    cout << "学生排名(按分数从高到低)：\n";
    while (!studentPQ.empty()) {
        Student top = studentPQ.top();
        cout << top.name << ": " << top.score << endl;
        studentPQ.pop();
    }
    
    return 0;
}

输出：

学生排名(按分数从高到低)：
Bob: 92
David: 90
Alice: 85
Charlie: 78
注意

在自定义比较函数中，return a < b;的含义是：如果a比b小，则a的优先级更低。这可能与直觉相反，需要特别注意。

Lambda表达式作为比较函数​

在C++11及以后的版本中，我们还可以使用Lambda表达式来定义比较函数：

cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
};

int main() {
    // 使用Lambda表达式按照点到原点的距离排序
    auto cmp = [](const Point& p1, const Point& p2) {
        int d1 = p1.x * p1.x + p1.y * p1.y;
        int d2 = p2.x * p2.x + p2.y * p2.y;
        return d1 > d2; // 距离小的优先级高
    };
    
    priority_queue<Point, vector<Point>, decltype(cmp)> pointPQ(cmp);
    
    pointPQ.push(Point(3, 4));  // 距离：5
    pointPQ.push(Point(1, 2));  // 距离：√5
    pointPQ.push(Point(5, 12)); // 距离：13
    pointPQ.push(Point(2, 2));  // 距离：2√2
    
    cout << "点按照到原点距离排序(从近到远)：\n";
    while (!pointPQ.empty()) {
        Point p = pointPQ.top();
        cout << "(" << p.x << "," << p.y << ") - 距离：" 
             << sqrt(p.x * p.x + p.y * p.y) << endl;
        pointPQ.pop();
    }
    
    return 0;
}

实际应用场景​

1. Dijkstra最短路径算法​

优先队列在图论算法中的应用非常广泛，例如Dijkstra最短路径算法：

cpp
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;

typedef pair<int, int> pii; // <距离, 顶点>

void dijkstra(vector<vector<pii>>& graph, int source) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[source] = 0;
    
    // 最小堆，按照距离排序
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, source});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        int d_u = pq.top().first;
        pq.pop();
        
        // 如果取出的距离大于当前已知距离，跳过
        if (d_u > dist[u]) continue;
        
        // 检查所有相邻顶点
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            // 松弛操作
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    // 输出最短距离
    cout << "从源点 " << source << " 到各点的最短距离：\n";
    for (int i = 0; i < n; i++) {
        cout << "顶点 " << i << ": " << (dist[i] == INT_MAX ? "不可达" : to_string(dist[i])) << endl;
    }
}

int main() {
    int n = 5; // 5个顶点
    vector<vector<pii>> graph(n);
    
    // 添加边 (u, v, weight)
    graph[0].push_back({1, 9});
    graph[0].push_back({2, 6});
    graph[0].push_back({3, 5});
    graph[0].push_back({4, 3});
    graph[2].push_back({1, 2});
    graph[2].push_back({3, 4});
    
    dijkstra(graph, 0);
    
    return 0;
}

2. 事件调度系统​

优先队列可以作为事件调度系统的核心组件，按照事件优先级或时间顺序处理事件：

cpp
#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Event {
    string name;
    int priority;
    int timestamp;
    
    Event(string n, int p, int t) : name(n), priority(p), timestamp(t) {}
};

struct EventCompare {
    bool operator()(const Event& e1, const Event& e2) {
        // 优先级高的先处理，优先级相同时按时间戳顺序处理
        if (e1.priority != e2.priority) {
            return e1.priority < e2.priority;
        }
        return e1.timestamp > e2.timestamp;
    }
};

class EventScheduler {
private:
    priority_queue<Event, vector<Event>, EventCompare> eventQueue;
    int currentTime;
    
public:
    EventScheduler() : currentTime(0) {}
    
    void addEvent(const string& name, int priority, int delay) {
        eventQueue.push(Event(name, priority, currentTime + delay));
        cout << "添加事件: " << name << " (优先级: " << priority 
             << ", 执行时间: " << currentTime + delay << ")\n";
    }
    
    void processNextEvent() {
        if (eventQueue.empty()) {
            cout << "没有待处理的事件\n";
            return;
        }
        
        Event e = eventQueue.top();
        eventQueue.pop();
        
        // 更新当前时间
        if (e.timestamp > currentTime) {
            currentTime = e.timestamp;
        }
        
        cout << "处理事件: " << e.name << " (优先级: " << e.priority 
             << ", 时间: " << currentTime << ")\n";
    }
    
    void processAllEvents() {
        while (!eventQueue.empty()) {
            processNextEvent();
        }
    }
    
    int getCurrentTime() const {
        return currentTime;
    }
};

int main() {
    EventScheduler scheduler;
    
    scheduler.addEvent("系统启动", 10, 0);
    scheduler.addEvent("低优先级后台任务", 1, 5);
    scheduler.addEvent("用户交互响应", 5, 3);
    scheduler.addEvent("重要系统通知", 8, 2);
    scheduler.addEvent("紧急报警", 10, 7);
    
    cout << "\n开始处理事件队列：\n";
    scheduler.processAllEvents();
    
    return 0;
}

时间复杂度​

优先队列基于堆实现，其主要操作的时间复杂度如下：

  • push(): O(log n)
  • pop(): O(log n)
  • top(): O(1)
  • size(): O(1)
  • empty(): O(1)

其中，n 是优先队列中元素的数量。

总结​

优先队列是一种非常实用的数据结构，它在许多算法和实际应用中都有重要作用：

  1. 特点：自动维护元素的优先级顺序，最高优先级元素始终位于队列顶部
  2. 实现：基于堆数据结构，默认为最大堆
  3. 用途：
    • 最短路径算法（如Dijkstra算法）
    • 事件调度系统
    • 任务调度
    • 模拟系统
    • 数据压缩算法（如霍夫曼编码）

优先队列的使用使得需要频繁获取最大/最小元素的操作变得高效，是学习STL容器中不可或缺的一部分。

练习题​

  1. 实现一个简单的任务管理系统，每个任务有名称、优先级和持续时间，按优先级高的先执行。
  2. 使用优先队列实现K个有序数组的合并。
  3. 修改上面的Dijkstra算法实现，使其能够同时输出最短路径。
  4. 实现一个医院急诊室的病人优先级排序系统。
  5. 使用优先队列解决"数据流中的第K大元素"问题。

进一步阅读​

  • 《C++ STL标准库》中关于优先队列的章节
  • 堆数据结构的详细实现和原理
  • 优先队列在高级算法中的应用，如A*搜索算法