以排序顺序保留前n个元素的最佳数据结构是什么？

Question

我正在寻找一个数据结构,它保留前n个元素,类似于这个问题,但增加了维护排序顺序的要求.显然我可以在最后排序,但可能有更有效的方法来实现它.只有插入,永远不会删除,然后通过末尾的前n个元素进行迭代.

这个问题与语言无关,但它将在C#中,因此使用本机.NET集合的答案更可取.

编辑:我应该澄清,排序顺序仅在前n个元素被迭代时才最重要.在插入过程中,只要保留前n个元素,排序顺序就无关紧要了.

Answer 1

如果您确实需要始终保持它们排序，则必须使用自平衡二叉搜索树。但请考虑到，这（保持元素排序）不是一种优化，而是一种有成本的奢侈。

自平衡二叉搜索树比隐式堆慢一个常数因子。

您想如何访问排序后的元素？如果只想迭代排序序列，普通的自平衡二叉搜索树就足够了。

如果您想随时按排序序列中的位置访问任何元素（另一种奢侈......），那么您需要扩充树。基本上，每个节点都会有一个附加字段来计算其子树中的节点数量，包括其自身。