c++固定大小的优先级队列来存储k-最近的邻居

Question

我正在树数据结构中实现 k 最近邻搜索。我将结果存储在一个优先队列中，它会自动按升序对元素进行排序，所以前 k 个元素就是结果。 STL 中的 priority_queue 容器在这里确实不是一个好的选择，因为它只支持 push()、pop()、top()、size() empty() 等少数函数。这里的一个大问题是，在搜索时整棵树，我需要访问很多节点，使用push()会使优先级队列越来越长，增加后面操作的时间成本。我真正想要的是一个固定长度的优先级队列，这样当 push() 一个新元素进入队列时，一些值较大的元素会被自动删除。我该如何实现？或者我可以使用任何标准容器吗？谢谢。

Answer 1

使用 std::set 怎么样？它按顺序存储元素，如果它增长到超过 k 元素，你可以只删除最大的一个(在恒定时间内)。每次插入都是 O(log k)。