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

user_8762103 0
Viewed 967

hash tables can insert in O(1), but they aren't sorted.

BSTs maintain an ordering (can be traversed using pre-order traversal) but insertion is O(logN).

is there any data structure that:

  1. guarantees O(1) insertion
  2. maintains an ordering over the elements?

if not, is there a proof that such a data structure cannot exist? thanks

binary-search-tree data-structures hashtable
2 Answers

In the general case, such a data structure is impossible because you could use it to sort a sequence with O(n) comparison operations, simply by inserting the sequence elements into it one-by-one. It is straightforward to show that Ω(n log n) is a lower bound for the number of comparisons required to sort a list, so insertion into a data structure which "maintains sorted order" must take at least Ω(log n) time per element.

Here I am assuming that it is possible to iterate over the data structure in order to output a sorted list, without doing any additional comparisons. If additional comparisons are required simply to iterate over the data structure's contents, then it is fair to say the data structure doesn't "maintain" sorted order internally. If you don't mind it taking O(n log n) time to iterate over a collection of size n, then you could just use an unsorted list as your data structure, with O(1) insertion time.

user_122990000

You can trade more space for this O(1). If the value domain is integral, say from 0 to N-1, then you could have a

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

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

For N values: O(N).

The difficulty (besides the value mapping, and 0 based indexing) is that the array is sparse: many zeroes. Hence the output is slow.

For unique values (as "hashtable" suggests), one can use BitSet in Java. This is also a bit faster on output (nextSetBit).

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

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