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

  • $\begingroup$ What kind of sorted data do you have, if it is numbers maybe you can use more memory to store some informations while building the data structure $\endgroup$ – someone12321 Jun 6 at 20:49
  • $\begingroup$ @someone12321 The current problem I am trying to solve stores objects holding a specific number. I think this reduces to the same problem you are mentioning (sorted numbers). Do you have a specific implementation in mind? $\endgroup$ – MathGeek Jun 6 at 21:06
  • 1
    $\begingroup$ @Apass.Jack I'm trying my best abstract away the details of my current problem. However, after my response to KhanPower I realized that I wasn't very clear. I will edit my question shortly. Basically I'm looking for a data structure that has logarithmic add and delete operations and can find the kth smallest element in constant time. Please ignore what I said about the sorted data. $\endgroup$ – MathGeek Jun 7 at 2:37
  • 1
    $\begingroup$ Is your $k$ fixed, or part of the query? $\endgroup$ – vonbrand Jun 28 at 16:54
  • 3
    $\begingroup$ @MathGeek: It is not self-evident. There is a well-known data structure called a finger tree that allows operations at a fixed position in the list to take constant worst-case time, for any given fixed position. So you must specify that the position is per-query. $\endgroup$ – user21820 Jul 8 at 16:15

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

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

  • $\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$ – Solomonoff's Secret Aug 7 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.