我正在树数据结构中实现 k 最近邻搜索。我将结果存储在优先级队列中，该队列会自动按升序对元素进行排序，因此前 k 个元素就是结果。 STL中的priority_queue容器在这里确实不是一个好的选择，因为它只支持push()、pop()、top()、size()、empty()等少数函数。这里的一个大问题是，当搜索时整棵树，我需要访问很多节点，而使用push()会让优先级队列越来越长，这会增加后面操作的时间成本。我真正想要的是一个固定长度的优先级队列，这样当push()一个新元素到队列中时，一些值较大的元素会被自动删除。我怎样才能实现这个？或者有我可以使用的标准容器吗？谢谢。
最佳答案
使用std::set怎么样？它按顺序存储元素，如果它增长到超过 k 个元素，您可以删除最大的一个(在恒定时间内)。每次插入都是 O(log k)。
关于C++ 固定大小的优先级队列来存储k近邻，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34488108/