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

  • 1
    $\begingroup$ Is a hash map not acceptable? It is O(1) for all the things you mentioned: en.wikipedia.org/wiki/Hash_table $\endgroup$ – hLk Jun 7 '19 at 0:37
  • $\begingroup$ @KhanPower The access time I'm referring to in the question is to get the value at an index for a list that is in sorted order. Because a hash table mixes up the ordering, getting the ith element aka the ith smallest/largest element would require resorting $\endgroup$ – MathGeek Jun 7 '19 at 0:45
  • $\begingroup$ @MathGeek What is that current problem you are trying to solve? Can you add a reference to that problem or explain that problem? $\endgroup$ – John L. Jun 7 '19 at 1:47
  • 2
    $\begingroup$ Would you settle for amortized $O(1)$ complexity? $\endgroup$ – Andrej Bauer Aug 7 '19 at 22:10
  • 1
    $\begingroup$ en.m.wikipedia.org/wiki/Skip_list#Indexable_skiplist is pretty close to what you want. $\endgroup$ – ryan Apr 4 at 1:49

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

  • 1
    $\begingroup$ I understand where you are coming from. But to me, even if an array is the only possible way to get constant lookup, I can't really say definitively that we wouldn't be able to lower the removal and insertion down to logarithmic time with some trickery (some pretty clever data structures can be implemented in an array alone like an array based heap for example which has many logarithmic operations). This would be different if you could somehow prove that you couldn't. As for the model fitting, I can't really make assumptions about the data. Also isn't the insertion into an array linear time? $\endgroup$ – MathGeek Jun 7 '19 at 3:55

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)$.

| cite | improve this answer | |
  • $\begingroup$ This answer assumes $k$ is fixed for the lifetime of the data structure, which the OP has clarified to not be the case. $\endgroup$ – Reinstate Monica Aug 7 '19 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.