C++优先队列模拟方法详解

• 使用 std::make_heap(v.begin(), v.end()) 构建堆
• 插入元素后调用 std::push_heap(v.begin(), v.end())
• 弹出最大元素前调用 std::pop_heap(v.begin(), v.end())，再 pop_back

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

std::vector<int> heap;

// 插入元素
heap.push_back(10);
std::push_heap(heap.begin(), heap.end()); // 维护最大堆

heap.push_back(5);
std::push_heap(heap.begin(), heap.end());

// 弹出最大元素
std::pop_heap(heap.begin(), heap.end()); // 把最大元素移到末尾
std::cout << heap.back() << "\n";       // 输出它
heap.pop_back();                         // 真正删除

#include <functional>

std::vector<int> min_heap;
// 所有操作加上比较器
std::push_heap(min_heap.begin(), min_heap.end(), std::greater<int>());
std::pop_heap(min_heap.begin(), min_heap.end(), std::greater<int>());

template<typename T = int, typename Compare = std::less<T>>
class MyPriorityQueue {
    std::vector<T> data;
public:
    void push(const T& val) {
        data.push_back(val);
        std::push_heap(data.begin(), data.end(), Compare{});
    }

    void pop() {
        std::pop_heap(data.begin(), data.end(), Compare{});
        data.pop_back();
    }

    const T& top() const { return data.front(); }
    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
};

MyPriorityQueue<int, std::greater<int>> pq;
pq.push(3); pq.push(1); pq.push(4);
while (!pq.empty()) {
    std::cout << pq.top() << " "; // 输出: 1 3 4
    pq.pop();
}