C++如何使用STL实现堆heap操作和priority_queue

make_heap

push_heap

pop_heap

priority_queue

<algorithm>

#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

<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);

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

priority_queue

make_heap