我不确定这是否可行，但对我来说似乎有点合理，我正在寻找一种允许我执行这些操作的数据结构:
- 用 O(log n) 插入一个项目
- 用 O(log n) 删除一个项目
- 查找/编辑 O(1) 中的第 k 个最小元素，对于任意 k(O(1) 索引)
当然，编辑不会导致元素顺序发生任何变化。使它成为可能的是我将按递增顺序一个一个地插入元素。因此，例如，如果我第五次尝试插入，我可以确定这之前的所有四个元素都小于它，而这之后的所有元素都会更大。
最佳答案
我不知道这样的数据容器是否可能达到所要求的时间复杂度。但这里有几种方法，几乎可以实现这些复杂性。
第一个是tiered vector插入和索引复杂度为 O(1)，删除复杂度为 O(sqrt N)。由于您预计此容器中只有大约 10000 个元素并且 sqrt(10000)/log(10000) = 7，因此您几乎可以在此处获得所需的性能。分层向量被实现为环形缓冲区数组，因此删除一个元素需要移动所有元素，在环形缓冲区中跟随它，并将一个元素从每个后续环形缓冲区移动到它之前的一个；在此容器中进行索引意味着在环形缓冲区数组中进行索引，然后在环形缓冲区内进行索引。
可以创建一个不同的容器，它与分层向量非常相似，具有完全相同的复杂性，但工作速度更快一些，因为它对缓存更友好。分配一个 N 元素数组来存储值。并分配一个 sqrt(N) 元素数组来存储索引校正(用零初始化)。我将在 100 元素容器的示例中展示它是如何工作的。要删除索引为 56 的元素，请将元素 57..60 移动到位置 56..59，然后在索引校正数组中将 1 添加到元素 6..9。要找到第 84 个元素，请在索引校正数组中查找第 8 个元素(其值为 1)，然后将其值添加到索引(84+1=85)，然后从主数组中取出第 85 个元素。主数组删除一半左右的元素后，需要对整个容器进行压缩，实现连续存储。这只会获得 O(1) 的累积复杂度。对于实时应用程序，此操作可以分几个较小的步骤执行。
这种方法可以扩展到 Trie深度为 M，索引时间为 O(M)，删除时间为 O(M*N1/M)，插入时间为 O(1)。分配一个N元素的数组来存储值，N(M-1)/M, N(M-2)/M, ..., N< sup>1/M - 用于存储索引修正的元素数组。要删除元素 2345，请在主数组中移动 4 个元素，在最大的“校正”数组中增加 5 个元素，在下一个数组中增加 6 个元素，在最后一个数组中增加 7 个元素。要从此容器中获取元素 5678，请将元素 5、56、567 中的所有更正添加到 5678，并使用结果索引主数组。为“M”选择不同的值，您可以平衡索引和删除操作之间的复杂性。例如，对于 N=65000，您可以选择 M=4；所以索引只需要4次内存访问和删除更新4*16=64个内存位置。
关于algorithm - 寻找一个 O(1) 索引和 O(log(n)) 插入和删除的数据容器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10478260/