在C++中自由实现"有界优先级队列"

Question

我正在寻找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

有谁知道这样的事情的良好实施？有经验吗？

Answer 1

我认为这个线程中讨论的算法可能就是您正在寻找的。如果您想抢占先机，您可能需要考虑构建 Boost 的实现，d_ary_heap_indirect该实现是 Boost.Graph 的一部分（参见 参考资料d_ary_heap.hpp）。如果你做得很好，你可以将它提交给 Boost。它可以做一个很好的补充，因为这样的实现肯定有很多用途。