空间有限的优先级队列:寻找一个好的算法

Question

这不是作业.

我正在使用一个小的"优先级队列"(目前实现为数组)来存储具有最小值的最后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实现(由少数人建议)比当前使用的线性阵列慢一点.

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

Answer 1

基于数组的堆似乎非常适合您的目的.我不确定你为什么拒绝他们.

您使用最大堆.

假设您有一个N元素堆(实现为数组),其中包含到目前为止看到的N个最小元素.

当一个元素进入时,检查max(O(1)时间),如果它更大则拒绝.

如果进入的值较低,则将root修改为新值并对此更改值进行筛选 - 最坏情况为O(log N)时间.

筛选过程很简单:从root开始,在每个步骤中将此值与其较大的子项交换,直到恢复max-heap属性.

因此, 如果使用std :: priority_queue,则不必执行任何可能需要删除的操作.根据std :: priority_queue的实现,这可能导致内存分配/释放.

所以你可以得到如下代码:

• 分配大小为N的阵列.
• 用你看到的前N个元素填充它.
• heapify(你应该在标准教科书中找到它,它使用sift-down).这是O(N).
• 现在你得到的任何新元素,你要么在O(1)时间内拒绝它,要么在最坏情况下O(logN)时间通过筛选来插入.

但是,平均而言,您可能不必一直向下筛选新值,并且可能比O(logn)平均插入时间更好(尽管我还没有尝试过证明它).

您只需分配大小为N的数组一次,并且通过交换数组的元素完成任何插入,因此之后没有动态内存分配.

查看具有heapify和sift-down伪代码的wiki页面:http://en.wikipedia.org/wiki/Heapsort

Answer 2

使用std::priority_queue与最大的头项目.对于每个新项目,如果它是>=头项目则丢弃它,否则弹出头项目并插入新项目.

旁注:标准容器只有在你成长的情况下才会增长.只要在插入新项目之前删除一个项目(当然,在它达到最大大小之后),就不会发生这种情况.