我正在寻找用 C++ 实现有界优先级队列抽象的免费软件。基本上，我需要一个数据结构，其行为与 std::priority_queue 一样，但始终最多包含“最佳”n 个元素。
例子:
std::vector<int> items; // many many input items
bounded_priority_queue<int> smallest_items(5);
for(vector<int>::const_iterator it=items.begin(); it!=items.end(); it++) {
smallest_items.push(*it);
}
// now smallest_items holds the 5 smallest integers from the input vector
有谁知道这样的事情的良好实现？有什么经验吗？
最佳答案
我认为 this thread 中讨论的算法可能是你要找的。如果您想抢先一步，您可能需要考虑构建 Boost 的实现 d_ary_heap_indirect，它是 Boost.Graph 的一部分(在 d_ary_heap.hpp 中)。如果你用它做得很好，你可以将它提交给 Boost。它可以做一个不错的小补充，因为这样的实现肯定有很多用途。
关于c++ - C++中 "bounded priority queue"的自由实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5329312/