相关疑难解决方法(0)

这不是作业.

我正在使用一个小的"优先级队列"(目前实现为数组)来存储具有最小值的最后N个项目.这有点慢 - O(N)项目插入时间.当前实现跟踪数组中的最大项并丢弃任何不适合数组的项,但我仍希望进一步减少操作数.

寻找符合以下要求的优先级队列算法:

1. queue可以实现为数组,它具有固定的大小和_cannot_ grow.严禁在任何队列操作期间进行动态内存分配.
2. 任何不适合数组的东西都会被丢弃,但是队列会保留所有遇到的最小元素.
3. O(log(N))插入时间(即将元素添加到队列中应占用O(log(N))).
4. (可选)O(1)访问队列中最大*项目(队列存储*最小*项目,因此最大项目将首先被丢弃,我需要它们来减少操作次数)
5. 易于实施/理解.理想情况下 - 类似于二元搜索的东西 - 一旦你理解它,你就会永远记住它.
6. 元素无需以任何方式排序.我只需要保持N遇到的最小值.当我需要它们时,我会立刻访问它们.所以从技术上讲,它不必是一个队列,我只需要存储N个最后的最小值.

我最初考虑使用二进制堆(它们可以通过数组轻松实现),但显然当数组不能再增长时它们表现不佳.链接列表和数组将需要额外的时间来移动东西.stl优先级队列增长并使用动态分配(尽管我可能错了).

那么,还有其他想法吗？

--EDIT--
我对STL实现不感兴趣.由于大量的函数调用,STL实现(由少数人建议)比当前使用的线性阵列慢一点.

我对优先级队列算法感兴趣,而不是实现.

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

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