C++中std::priority_queue的使用小结-牛翰网

1. 基本用法

(1) 头文件

要使用 std::priority_queue，需要包含：

#include <queue>
#include <vector>
#include <iostream>

(2) 默认情况（最大堆）

默认情况下，std::priority_queue 是最大堆，即堆顶是最大元素：

std::priority_queue<int> pq;  // 默认是最大堆

示例：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "堆顶元素：" << pq.top() << std::endl;  // 输出 30

    pq.pop();  // 移除 30
    std::cout << "新的堆顶：" << pq.top() << std::endl;  // 输出 20

    return 0;
}

特点

push() 插入元素，自动维护最大堆。
top() 获取当前最大元素（堆顶）。
pop() 移除堆顶元素（但不返回它）。
size() 获取队列大小。
empty() 检查队列是否为空。

2. 自定义最小堆

如果要实现最小堆（堆顶是最小元素），可以用 std::greater<T>：

std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;

示例：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;

    pq_min.push(10);
    pq_min.push(30);
    pq_min.push(20);

    std::cout << "堆顶元素：" << pq_min.top() << std::endl;  // 输出 10

    pq_min.pop();
    std::cout << "新的堆顶：" << pq_min.top() << std::endl;  // 输出 20

    return 0;
}

重点

std::greater<int> 使 priority_queue 变成最小堆。

3. 自定义比较函数（结构体/仿函数）

(1) 结构体仿函数

struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // 最小堆（a > b 表示 a 在 b 下面）
    }
};
std::priority_queue<int, std::vector<int>, Compare> pq;

示例：

#include <iostream>
#include <queue>

struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // 让小的元素优先级高
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, Compare> pq;

    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "堆顶元素：" << pq.top() << std::endl;  // 输出 10

    pq.pop();
    std::cout << "新的堆顶：" << pq.top() << std::endl;  // 输出 20

    return 0;
}

优点

适用于复杂的数据结构（如 struct）。
允许灵活定义优先级。

4. 处理结构体类型

如果 priority_queue 存储的是自定义结构体，需要提供比较规则。

(1) 按权重排序的任务调度

#include <iostream>
#include <queue>

struct Task {
    int id;
    int priority;

    // 重载运算符，用于最大堆（优先级大的优先）
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 优先级高的排前面
    }
};

int main() {
    std::priority_queue<Task> pq;

    pq.push({1, 3});
    pq.push({2, 5});
    pq.push({3, 1});

    std::cout << "最高优先级任务 ID：" << pq.top().id << std::endl;  // 输出 2

    pq.pop();
    std::cout << "新的最高优先级任务 ID：" << pq.top().id << std::endl;  // 输出 1

    return 0;
}

特点

默认是最大堆，因此 operator< 定义为优先级小的在下面。

(2) 使用自定义比较函数

如果不能修改 struct，可以使用外部比较函数：

struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;  // 最小堆
    }
};

std::priority_queue<Task, std::vector<Task>, CompareTask> pq;

完整示例：

#include <iostream>
#include <queue>

struct Task {
    int id;
    int priority;
};

// 使 priority_queue 变成最小堆
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;  // 小优先级的任务优先
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> pq;

    pq.push({1, 3});
    pq.push({2, 5});
    pq.push({3, 1});

    std::cout << "最高优先级任务 ID：" << pq.top().id << std::endl;  // 输出 3

    pq.pop();
    std::cout << "新的最高优先级任务 ID：" << pq.top().id << std::endl;  // 输出 1

    return 0;
}

适用场景

优先队列调度算法
事件驱动仿真
A 搜索（最短路径算法）*

5. priority_queue 适用场景

应用场景	用法
最大堆（默认）	std::priority_queue<int>
最小堆	std::priority_queue<int, std::vector<int>, std::greater<int>>
存储结构体（最大堆）	结构体重载 <
存储结构体（最小堆）	std::greater<> 或自定义 Compare
K 大/小元素	维护大小为 K 的堆
Dijkstra / A 搜索*	结合 std::pair<int, int> 进行路径计算

6. 经典应用示例

(1) 找到前 K 个最大元素

#include <iostream>
#include <queue>
#include <vector>

void findTopK(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 最小堆

    for (int num : nums) {
        pq.push(num);
        if (pq.size() > k) pq.pop();  // 只保留 k 个最大值
    }

    std::cout << "前 " << k << " 个最大元素：" << pq.top() << std::endl;
}

int main() {
    std::vector<int> nums = {3, 1, 5, 12, 2, 11};
    findTopK(nums, 3);  // 输出 5
}

复杂度：O(N log K)