是否有 O(1) 插入时间的数据结构也保持排序顺序？

Question

哈希表可以在 O(1) 中插入，但它们未排序。

BST保持一个顺序（可以使用前序遍历来遍历）但是插入是O(logN)。

是否有任何数据结构：

保证 O(1) 插入
维护元素的顺序？

如果不是，是否有证据表明这样的数据结构不存在？谢谢

Answer 1

您可以用更多 space 换取这个 O(1)。如果值域是整数，比如从 0 到 N-1，那么你可以有一个

// (In Java)
int[] valueToFrequency = new int[N];

void insert(int value) {
    ++valueToFrequency[value];
}

对于 N 个值：O(N).

困难（除了值映射和基于 0 的索引之外）是数组是稀疏的：许多零。因此输出很慢。

对于唯一值（如“哈希表”所建议的），可以在 Java 中使用 BitSet。这在输出 (nextSetBit) 上也更快一些。

// (In Java)
BitSet valueToFrequency = new Bitset(N);

void insert(int value) {
    valueToFrequency.set(value);
}

Answer 2

在一般情况下，这样的数据结构是不可能的，因为您可以使用它对具有 O(n) 比较操作的序列进行排序，只需将序列元素一个一个地插入其中即可。很容易证明 Ω(n log n) 是 number of comparisons required to sort a list 的下界，因此插入到“保持排序顺序”的数据结构中每个元素至少需要 Ω(log n) 时间。

这里我假设可以迭代数据结构以输出排序列表，而无需进行任何额外的比较。如果只是为了迭代数据结构的内容而需要额外的比较，那么可以公平地说数据结构不会在内部“维护”排序顺序。如果您不介意用 O(n log n) 时间遍历大小为 n 的集合，那么您可以只使用未排序的列表作为数据结构，插入时间为 O(1)。

是否有 O(1) 插入时间的数据结构也保持排序顺序？

is there a data structure with O(1) insertion time which also maintains sorted order?

data-structures

binary-search-tree

hashtable