Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

Question

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in logarithmic time. The closest I've found to this is the order statistic tree which achieves logarithmic add and delete operations but has logarithmic time complexity for accessing the kth smallest element.

Any ideas along these lines would be much appreciated.

Clarification: kth smallest means that for any variable k value (non-constant), the data structure should be able to retrieve that value

Answer 1

An array is the only thing that will get you consistent lookup in constant time.

Removal & Insertion time $\in O(n)$

If you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal

Answer 2

Kth smallest number in a dynamic stream of numbers. Idea from the above source.

Have two heaps, one a max heap with $k$ elements (all the elements less than the $k$th largest element and the $k$th largest element itself are here) and the rest of the elements are in the other min heap.

1. Inserting a new element: If the new element is less than the top of the max heap (which is the current $k$th largest element), then insert it into the max heap, after that (I mean to say after the heapification following the insertion) pop the top element and insert it into the min heap. If the new element is greater than or equal to the current $k$th largest insert it into the min heap.

2. Deletion: If the element is in the min heap (ie., greater than equal to the $k$th largest) then simply delete from the min heap*. Else delete the element from the max heap and pop the top of the min heap and insert it into the max heap.

3. Look up: simply output the top of the min heap. You'll have to suitably handle the corner case where there aren't enough elements ie. the total number of elements are less than $k$.

Please look into deletion of element in $O(\log n)$ time. It's a little complicated – you've gotta keep track of the positions of the elements in the heap so that you have $O(\log n)$ if you use a set (in C++) or $O(1)$ amortized if you use hash tables/unordered set. After finding the element in heap you've gotta replace it with the last element in the heap and let it sift down or up, which is $O(\log n)$.