我需要一个始终保存迄今为止插入的最大项目的数据结构（无特定顺序）。
因此，如果
n为 3，我们可以进行以下会话，其中我插入一些数字并且容器的内容会发生变化：
n
你明白了。数据结构的名称是什么？实现这一点的最佳方法是什么？或者这个在某个图书馆里？
我正在考虑使用一个其元素（委托）具有
[] // now insert 1
[1] // now insert 0
[1,0] // now insert 4
[1,0,4] // now insert 3
[1,4,3] // now insert 0
[1,4,3] // now insert 3
[4,3,3]
的容器，它使用反向比较，因此
priority_queuepop（我心里有一个
insert实现，但问题仍然与语言无关。）
这个想法是将数组（称之为 A）视为深度为 n 的完全二叉树：
忽略A[0]；将A[1]视为根节点 对于每个节点 A[k]，子节点是 A[2*k] 和 A[2*k+1]在 Java 中，你可以使用 SortedSet 实现，例如通过 TreeSet。每次插入后检查集合是否太大，如果是则删除最后一个元素。
priority_queue 是 C++ 中与 STL 最接近的东西。您可以将其包装在另一个类中以创建您自己的自动修剪大小的实现。
插入数据
排序
A
有界优先级队列在 Pyhton 中，使用 heapq。在它周围创建一个小包装，如下所示：
...
是的，您可以保持 N 号的最小头部 然后在每次插入时将新项目与根项目进行比较 如果根项“大于”根项，则弹出根项并插入该项 最后你得到了 N 个最大的物品
这是 C++ 11 中的一个简单实现。 可能不是最好的，但易于使用且简洁。
输出：
#include <iostream>
#include <map>
/// @brief Maintains a set of N elements with the best keys. (duplicate keys are allowed)
template<class Key, class T, class Compare = std::less<Key> >
class KeepNBests{
public:
KeepNBests(size_t N=0):N(N), is_less(Compare()){}
bool add(const Key& key, const T& t){
// If there are enough elements,
if(bests.size()>N // and the candidate key is worse than the worst stored key...
&& is_less(key, bests.cbegin()->first)){
return false; // nothing to do
}
// else insert the new candidate
bests.insert({key, t});
// keeps max N elts
while(bests.size()>N){
bests.erase(bests.cbegin());
}
return true;
}
const std::multimap<Key, T, Compare>& get()const{
return bests;
}
public:
const size_t N;
private:
Compare is_less;
std::multimap<Key, T, Compare> bests;
};
int main() {
KeepNBests<double, std::string> best(3);
best.add(0., "bad");
best.add(0., "bad");
best.add(300., "the best");
best.add(10., "ok");
best.add(-1., "bad");
best.add(-7., "very bad");
best.add(-1., "bad");
best.add(100., "good");
best.add(2., "bof");
best.add(200., "the second");
for(const auto& b : best.get()){
std::cout << b.first << " " << b.second << std::endl;
}
return 0;
}
创建一个最小堆，同时存储一个计数器。
您可以通过以下方式执行此操作：O(1) insert、get-min 和 O(log log n) extract-min。
100 good
200 the second
300 the best
或者，您可以使用 O(log n) insert 和 O(1) 执行另一个操作提到的操作。
[1][2] M. Thorup，“常数时间内密钥递减的整数优先级队列和单源最短路径问题”，第 35 届 ACM 计算理论年度研讨会论文集，美国纽约，2003 年，第 149–158 页。[1]