algorithm - timsort 和手动维护排序序列，哪个效率更高？

Question

我正在开发一个启发式例程，需要维护一个排序的序列/数组/列表。我听说 timsort 可以快速维护具有已排序子序列的序列的顺序。

另一方面，我需要的很简单。在对序列进行初步排序后，我需要在每个步骤中重复执行以下操作之一:

1. 删除最小元素。

2. 访问每个最小的 K 元素。

3. 插入一个元素并保持顺序。

timsort 似乎具有 O(n) 的最佳情况复杂度。天真地，我可以通过调用 timsort 得到 O(n) 来实现操作 3。但是这些操作需要重复很多次。我想知道手动维护排序序列(数组或列表)或在每一步执行 partial_sort 是否会更快，如果是这样，有什么复杂性。

为了公开，我使用 c++，必要时使用 c++/c++11 的示例会很好。

谢谢，

Answer 1

似乎最好的方法是实际使用自平衡二叉搜索树。如果我没记错的话，这应该处理 O(log N) 中的插入/删除并迭代 O(k) 中的 k 最小元素。除非出于某种原因，否则必须使用列表。