基于数组的堆似乎很适合您的目的。我不确定你为什么拒绝他们。
您使用最大堆。
假设您有一个N元素堆（实现为数组），其中包含到目前为止所见的N个最小元素。
当元素进入时，请检查最大时间（O（1）时间），如果大于则拒绝。
如果输入的值较低，则将根修改为新值，然后向下筛选该更改的值-最坏的情况是O（log N）时间。
筛选过程很简单：从根开始，在每个步骤中，您都用它的较大子项交换此值，直到恢复max-heap属性。
因此， 如果使用std :: priority_queue，则不必进行任何可能必须 删除的操作 。根据std ::
priority_queue的实现，这可能导致内存分配/重新分配。
因此，您可以拥有如下代码：
- 大小为N的已分配数组。
- 用您看到的前N个元素填充它。
- heapify（您应该在标准教科书中找到它，它使用sift-down）。这是O（N）。
- 现在，您得到的任何新元素都可以在O（1）时间内拒绝它，或者在最坏的情况下通过筛选O（logN）时间来插入。
但是，平均而言，您可能不必完全筛选新值，并且可能会比O（logn）平均插入时间更好（尽管我尚未尝试证明）。
您只分配一次大小为N的数组，并且任何插入都是通过交换数组的元素来完成的，因此此后没有动态内存分配。
请查看Wiki页面，该页面具有用于heapify和sift-
down的伪代码：http :
//en.wikipedia.org/wiki/Heapsort
