相关疑难解决方法(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实现(由少数人建议)比当前使用的线性阵列慢一点.

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

我正在寻找一种执行快速排序插入的数据结构,并基于FIFO进行操作.

我想要实现的是一个固定大小的数据结构来保存一系列值.在迭代的每个新步骤中,我希望能够有效地找到最小值或最大值(因此我希望数据结构始终被排序),并且在请求插入新元素时,最旧的元素将自动生成(或至少能够有效地)弹出/丢弃.

所以我想我正在寻找某种FIFO优先级队列.

任何帮助非常感谢.