用于插入/排序的最快数据结构

Question

我需要一个可以插入元素并尽快排序的数据结构.我将插入比排序更多.删除不是一个问题,而是空间.我的具体实现还会将节点存储在一个数组中,因此查找将为O(1),即您不必担心它.

Answer 1

只需使用其中一个自平衡二叉搜索树,例如红黑树.

Answer 2

如果要插入一个很多比排序越多,那么它可能是最好使用一个未排序的列表/矢量,当你需要它排序快速排序它.这样可以非常快速地插入.所述一个¹缺点是,排序是相对冗长的操作,因为它不是在许多插入摊销.如果你依赖相对恒定的时间,这可能是坏事.

_{¹想想看,还有第二个缺点.如果您低估了排序频率,这可能很快就会比树或排序列表慢一些.例如,如果您在每次插入后排序,那么insert + quicksort循环将是个坏主意.}