C++ STL堆操作与priority_queue用法详解

C++中堆操作可通过STL算法函数和priority_queue容器适配器实现。1. 使用<al algorithm>中的make_heap、push_heap、pop_heap可在vector等容器上构建和操作堆，默认为最大堆，通过greater<int>可实现最小堆；2. priority_queue定义于<queue>头文件，封装了堆操作，使用更简便，支持自定义比较函数和结构体排序，推荐用于常规场景。

在C++中，堆操作和优先队列可以通过STL中的 算法函数 和 容器适配器 来实现。主要涉及 make_heap、push_heap、pop_heap 等算法，以及更方便的 priority_queue 容器适配器。

使用算法实现堆操作

STL 提供了一组算法用于在普通容器（如 vector）上执行堆操作。这些函数定义在 <algorithm> 头文件中。

• make_heap(first, last)：将区间 [first, last) 构造成一个最大堆
• push_heap(first, last)：假设前 n-1 个元素是堆，将最后一个元素插入堆中
• pop_heap(first, last)：将堆顶元素移到末尾，前 n-1 个元素仍为堆
• is_heap(first, last)：判断是否为堆

使用示例：

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2};

    // 构建最大堆
    std::make_heap(v.begin(), v.end());

    // 输出堆顶
    std::cout << "Top: " << v.front() << "\n";  // 输出 9

    // 插入元素
    v.push_back(7);
    std::push_heap(v.begin(), v.end());

    std::cout << "New top: " << v.front() << "\n";  // 输出 9 或 7

    // 弹出堆顶
    std::pop_heap(v.begin(), v.end());
    int top = v.back();
    v.pop_back();
    std::cout << "Popped: " << top << "\n";

    return 0;
}

自定义比较函数（实现最小堆）

默认是最大堆。要实现最小堆，可以传入比较函数，比如 std::greater<int>。

std::vector<int> v = {3, 1, 4, 1, 5};
std::make_heap(v.begin(), v.end(), std::greater<int>());

v.push_back(0);
std::push_heap(v.begin(), v.end(), std::greater<int>);

使用 priority_queue（推荐方式）

priority_queue 是 STL 提供的堆容器适配器，封装了堆操作，使用更简单。定义在 <queue> 头文件中。

基本用法：

#include <queue>
#include <iostream>

std::priority_queue<int> max_heap;  // 最大堆
max_heap.push(3);
max_heap.push(1);
max_heap.push(4);

std::cout << max_heap.top() << "\n";  // 输出 4
max_heap.pop();                        // 移除 4

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(3);
min_heap.push(1);
min_heap.push(4);
std::cout << min_heap.top() << "\n";  // 输出 1

struct Task {
    int priority;
    std::string name;
};

// 自定义比较：优先级小的先出（最小堆）
auto cmp = [](const Task& a, const Task& b) {
    return a.priority > b.priority;
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);

priority_queue 模板参数说明

其定义为：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

• T：元素类型
• Container：底层容器，默认 vector
• Compare：比较函数，默认 less（最大堆）

基本上就这些。直接用 priority_queue 更简洁，适合大多数场景。需要灵活控制时再用 make_heap 等算法。