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

Question

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

Answer 1

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.