优先级队列空间有限：寻找一个好的算法 [英] priority queue with limited space: looking for a good algorithm

问题描述

这是不是一门功课。

我用一个小的优先级队列（实现为阵的那一刻），用于存储与最小的价值最后N项。这是一个有点慢 - O（N）项目插入时间。当前实现跟踪大项目的阵列，并丢弃，将不适合阵列的任何物品，但我还是想进一步减少操作次数。

找了优先级队列算法匹配下列要求：

1. 队列可以实现为阵列，它具有固定的大小和_cannot_生长。任何队列运行过程中动态内存分配是严格禁止的。
2. 任何不适合阵列被丢弃，但队列中不断遇到过的所有最小元素。
3. O（日志（N））的插入时间（即添加元素插入队列应该达到O（日志（N）））。
4. 的（可选）O（1）访问*大*的队列项（队列存储*最小*的项目，所以最大的项目将被丢弃第一，我需要他们减少操作次数）
5. 易于实施/理解。理想的情况是 - 类似二进制搜索的东西 - 一旦你了解它，你永远记住它。
6. 元素需要不以任何方式进行排序。我只需要保持遇到过n个最小值。当我需要他们，我将访问所有这些一次。所以，从技术上它并没有成为一个队列，我只需要ň最后最小值被存储。

我最初想过用二进制堆（他们可以通过阵列易于实现），但显然他们不守规矩时，阵列不能再生长。链表和数组将需要额外的时间来移动周围的事物。 STL优先级队列的增长和使用动态分配的（我的可以的是错的吧，虽然）。

因此​​，任何其他的想法？

- EDIT--
我不感兴趣的STL实现。 STL实现（由少数人所建议的）作品有点慢于目前使用的线性阵列，由于大量的函数调用。

我感兴趣的优先级队列中的算法的，不implemnetations。

解决方案

基于阵列堆看起来非常适合你的目的。我不知道你为什么拒绝了他们。

您使用一个最大堆。

假设你有N元素堆（实现为一个数组），其中包含了n个最小元素见过这么远。<​​/ P>

当一个元素进来，你核对最大（（1）时间O），并拒绝如果它是更大的。

如果该值进来的越低，你修改根成为新的价值和整理下这个变化值 - 最差情况为O（log n）时间

在筛下来的过程很简单：起价根，每一步你交流这方面的价值与它的大孩子，直到最大堆属性恢复

那么，你会不会做任何的删除的，你可能要，如果你使用std :: priority_queue。根据的std :: priority_queue的实现，这可能导致内存分配/释放。

所以，你可以有code如下：

• 在大小为N分配的数组。
• 与你看到的第N个元素填充它。
• heapify（你会发现这个标准教科书，它采用筛下）。这是O（N）。
• 现在，你得到任何新的元素，你要么拒绝它的O（1）时间或在最坏的情况下O（logN）的时间筛选下来插入。

在一个平均，不过，你可能不会有筛选下的新值一路下滑，并可能会比O（LOGN）平均插入时间更好（虽然我还没有尝试过，证明它）。

您只分配大小N阵列一次和任何插入通过交换所述阵列的元件完成的，所以没有动态内存分配之后

退房的维基网页，其中有伪$ C $下heapify和筛选下来： HTTP：//en.wikipedia。组织/维基/堆排序

This is not a homework.

I'm using a small "priority queue" (implemented as array at the moment) for storing last N items with smallest value. This is a bit slow - O(N) item insertion time. Current implementation keeps track of largest item in array and discards any items that wouldn't fit into array, but I still would like to reduce number of operations further.

looking for a priority queue algorithm that matches following requirements:

1. queue can be implemented as array, which has fixed size and _cannot_ grow. Dynamic memory allocation during any queue operation is strictly forbidden.
2. Anything that doesn't fit into array is discarded, but queue keeps all smallest elements ever encountered.
3. O(log(N)) insertion time (i.e. adding element into queue should take up to O(log(N))).
4. (optional) O(1) access for *largest* item in queue (queue stores *smallest* items, so the largest item will be discarded first and I'll need them to reduce number of operations)
5. Easy to implement/understand. Ideally - something similar to binary search - once you understand it, you remember it forever.
6. Elements need not to be sorted in any way. I just need to keep N smallest value ever encountered. When I'll need them, I'll access all of them at once. So technically it doesn't have to be a queue, I just need N last smallest values to be stored.

I initially thought about using binary heaps (they can be easily implemented via arrays), but apparently they don't behave well when array can't grow anymore. Linked lists and arrays will require extra time for moving things around. stl priority queue grows and uses dynamic allocation (I may be wrong about it, though).

So, any other ideas?

--EDIT--
I'm not interested in STL implementation. STL implementation (suggested by a few people) works a bit slower than currently used linear array due to high number of function calls.

I'm interested in priority queue algorithms, not implemnetations.

解决方案

Array based heaps seem ideal for your purpose. I am not sure why you rejected them.

You use a max-heap.

Say you have an N element heap (implemented as an array) which contains the N smallest elements seen so far.

When an element comes in you check against the max (O(1) time), and reject if it is greater.

If the value coming in is lower, you modify the root to be the new value and sift-down this changed value - worst case O(log N) time.

The sift-down process is simple: Starting at root, at each step you exchange this value with it's larger child until the max-heap property is restored.

So, you will not have to do any deletes which you probably will have to, if you use std::priority_queue. Depending on the implementation of std::priority_queue, this could cause memory allocation/deallocation.

So you can have the code as follows:

• Allocated Array of size N.
• Fill it up with the first N elements you see.
• heapify (you should find this in standard text books, it uses sift-down). This is O(N).
• Now any new element you get, you either reject it in O(1) time or insert by sifting-down in worst case O(logN) time.

On an average, though, you probably will not have to sift-down the new value all the way down and might get better than O(logn) average insert time (though I haven't tried proving it).

You only allocate size N array once and any insertion is done by exchanging elements of the array, so there is no dynamic memory allocation after that.

Check out the wiki page which has pseudo code for heapify and sift-down: http://en.wikipedia.org/wiki/Heapsort

这篇关于优先级队列空间有限：寻找一个好的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！