我需要一种数据结构，可以尽快地插入元素并对自身进行排序。我将插入的数量远远多于排序的数量。删除操作不是很重要，空间也不是问题。我的具体实现还将节点存储在数组中，因此查找时间为O（1），也就是说您不必担心这个问题。
最快的数据结构用于插入/排序
8
- someguy
4
如果你通过数组查找，为什么需要数据结构被排序呢？每次插入后它需要保持有序吗？ - Chris Card
是的，在插入后需要按顺序排列。我不会直接索引元素，而是节点，它应该可以访问其相邻节点。 - someguy
你自相矛盾了。问题说“我将插入的数量比排序多得多”，但是你的评论说“每次插入后都需要按顺序排列”。如果前者是正确的，那么我的答案可能是合适的。如果后者是正确的，那么最好使用树，就像squadette建议的那样（尽管我不确定它需要平衡，因为查找并不是什么大问题）。 - P Daddy
糟糕，我没有好好思考。我的意思是每次插入后它不必须按顺序排列。抱歉。 - someguy
6个回答
7
只需要使用其中一种自平衡二叉搜索树，例如红黑树。
- squadette
2
我在想是否有更快的东西，而且我想手动平衡/排序。 - someguy
1如果您想在每次插入后进行排序，并且元素数量是任意的，以至于您不能为每个项目都设置桶，那么树就是最好的选择。这将在同一操作中插入和排序；恐怕您不会得到比这更快的速度了。 - thecoop
7
如果你需要插入的数量比排序要多很多，那么最好使用未排序列表/向量，并在需要进行排序时进行快速排序。这样可以保持插入非常快速。唯一的缺点是，由于它不是在许多插入上分摊的，所以排序是一个相对较长的操作。如果你依赖相对恒定的时间，这可能会很糟糕。
顺便提一下，还有第二个缺点。如果你低估了排序频率，这可能很快就会比树或排序列表慢。例如，如果你每次插入后都进行排序，那么插入+快速排序的循环就是一个坏主意。
顺便提一下，还有第二个缺点。如果你低估了排序频率，这可能很快就会比树或排序列表慢。例如，如果你每次插入后都进行排序，那么插入+快速排序的循环就是一个坏主意。
- P Daddy
3
“虽然我不确定它是否需要像他建议的那样平衡，因为查找并不是什么大问题”，但如果它是平衡的，插入会更快吗？P.S. “查找”并不是指搜索。 - someguy
@someguy：好吧，这取决于实际发生了多少平衡开销和它防止了多少遍历。 - P Daddy
你可以对排序方法进行优化。如果你为列表/向量创建一个包装器，你就可以跟踪已经排序的部分（它是列表的前面，所以你只需要一个单一的索引）。然后当你想重新排序时，你只需要对未排序的部分进行排序和合并。这样复杂度就远远小于正常的O(n log n)排序。 - Jeremy West
2
如果您不需要随机访问数组，请使用堆。
最坏和平均时间复杂度：
- O(log N) 插入
- O(1) 读取最大值
- O(log N) 删除最大值
可以重新配置以提供最小值而不是最大值。通过反复删除最大/最小值，您可以在O(N log N)中获得排序列表。
- Isaac Turner
2
使用任何一种平衡二叉树，如AVL树。这应该为您寻找的两个操作提供O(lg N)的时间复杂度。
- sadakurapati
1
如果您在每个排序之前可以执行大量插入，则显然应该只附加项目并在必要时尽快进行排序。我的最爱是归并排序。这是O（N * log（N）），行为良好，并且最小化了存储操作（new，malloc，tree balancing等）。
但是，如果集合中的值是整数并且相对密集，则可以使用O（N）排序，在其中只使用每个值作为一个足够大的数组的索引，并在该索引处设置布尔值TRUE。然后，您只需扫描整个数组并收集TRUE的索引即可。
您说您正在将项目存储在查找为O（1）的数组中。除非您使用哈希表，否则这表明您的项目可能是密集整数，因此我不确定您是否甚至拥有问题。
无论如何，内存分配/删除都很昂贵，您应该通过预分配或汇集来避免它。
但是，如果集合中的值是整数并且相对密集，则可以使用O（N）排序，在其中只使用每个值作为一个足够大的数组的索引，并在该索引处设置布尔值TRUE。然后，您只需扫描整个数组并收集TRUE的索引即可。
您说您正在将项目存储在查找为O（1）的数组中。除非您使用哈希表，否则这表明您的项目可能是密集整数，因此我不确定您是否甚至拥有问题。
无论如何，内存分配/删除都很昂贵，您应该通过预分配或汇集来避免它。
- Mike Dunlavey
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接