Optimal data structure and algorithm for getting the k'th element

user_9837518 0
Viewed 114

I'm given a set of n elements. Is there a data structure with a build time (pre processing) of O(n). and from then on can answer queries to get the k'th largest element in O(k)? Is there anything better than O(k)?

data-structures algorithm
1 Answers

Sketching out my comment for a O(n) build time and O(k log k) search time for the kth largest element.

Preprocessing is just building a heap h which can be done in O(n)

Then during query time you have to use an additional priority queue q where elements are ordered by value (descending). The algorithm works as follows:

  • start by putting the root node of h into q

  • now repeat k times: remove the head of q and put the children of this element (according to h) in q

  • the last element removed is your kth largest element

Removing an element from q (which is itself a heap) is O(|q|). In each step q will grow by 1 element. After k-1 steps it will have a size of k. Thus this algorithm runs in O(k log k)

user_85926470
Related