c# - 结构比 SortedSet 更快地添加 1-by-1，然后从末尾访问少量项目

Question

我正在浏览 List<> ，对每个项目执行一些操作，然后根据这些操作的结果，可能将每个添加到另一个数据结构，我目前正在为此使用 SortedSet<> .在此之后，我想要排名靠前的 n项目作为列表。

我必须为此做的唯一一件事 SortedSet<>是清除整件事并重新开始。有什么方法可以让我从中获得更多的性能？

我看到了this similar question张贴者使用自定义红黑树(在他们的问题得到回答后)能够将运行时间减少大约 1/6。但是 SortedSet<> 不是已经是红黑树了吗？在这种情况下，通过创建自己的数据结构来尝试提高性能是否值得？

Answer 1

您可以尝试通过不为程序未使用的内容“付费”来获得更好的性能:您可以使用 heap 而不是使用使所有元素排序的树结构。它不会对元素进行排序，但可以让您在 k * log(n) 时间内提取 k 最大的元素。

堆在插入和删除方面往往比平衡树更快，而且它们还占用连续的内存区域，这在某些情况下可能会提高“缓存友好性”。当然，加速不是免费的:堆不支持快速排序或移除顶部以外的项目。