c++中如何模拟优先队列_c++优先队列模拟方法-C++-PHP中文网

c++中如何模拟优先队列_c++优先队列模拟方法

冰火之心

发布： 2025-09-30 10:39:02

原创

887人浏览过

答案：可通过vector配合堆操作函数模拟优先队列。①用push_back插入元素后调用push_heap维持堆序；②弹出时先pop_heap将首元素移至末尾再pop_back；③自定义比较器可实现最小堆；④可封装类实现类似priority_queue接口；⑤该方式比标准容器更灵活，适用于需访问内部元素的场景。

c++中如何模拟优先队列_c++优先队列模拟方法

在C++中，优先队列（priority queue）可以通过标准库中的 std::priority_queue 直接使用。但如果你想手动模拟一个优先队列的行为，可以借助 std::vector 或 std::deque 配合 堆操作函数 std::make_heap、std::push_heap、std::pop_heap 来实现。这种方式能更灵活地控制底层逻辑，比如访问内部元素或修改优先级。

使用 vector 模拟优先队列

你可以用 vector 存储元素，并通过堆操作保持堆结构：

使用 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();                         // 真正删除

登录后复制

自定义比较函数（最小堆为例）

默认是最大堆，若要模拟最小堆，传入 std::greater：

立即学习“C++免费学习笔记（深入）”；

天谱乐

唱鸭旗下AI音乐创作平台，为您提供个性化音乐创作体验！

514

查看详情

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

登录后复制

封装成类模拟 priority_queue

可以封装成类似 std::priority_queue 的接口：

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

登录后复制

使用方式和 std::priority_queue 基本一致：

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

登录后复制

基本上就这些。手动模拟有助于理解堆的工作机制，也适用于需要干预队列内部状态的场景。标准 priority_queue 更简洁，而 vector + 堆操作更灵活。根据需求选择即可。

以上就是c++++中如何模拟优先队列_c++优先队列模拟方法的详细内容，更多请关注php中文网其它相关文章！