Xtykutl

Suppose you get numbers all the time and you don't know how many numbers will come at the beginning. At any time I want to be able to output the largest number and the n/3 largest number (where n is the number of numbers entered up to this point) immediately (in O(1)). The maximum time for entering new numbers is O(log(n)).

What is the best way to implement this ?

You could implement it with two heaps: a min-heap (A), and a max-heap (B).

The idea is to store in A the n/3 greatest values, and the rest in B so that the maximum in B is the n/3 greatest value (counting zero-based). Assuming that n/3 is truncated down in case n is not a multiple of three, and that the resulting value is zero-based (n/3 == 0 means the maximum is also the n/3 greatest element), this means that the following invariance must be maintained:

A.size == floor((A.size + B.size)/3)

...which comes down to:

0 <= B.size - 2*A.size < 3 

The above condition might vary a bit depending on the interpretation what the n/3 element is (is it 0-based, 1-based, rounded, truncated,...), and some special care might be needed when there are fewer than 3 elements in the total collection, depending on that definition.

For adding a value v you would first decide in which heap it belongs. If it is smaller than the current n/3^th greatest value -- the max value in B -- then it belongs in B, otherwise in A. After that addition the invariance might be broken and must be restored by pulling one value from either heap and adding it to the other.

More formally v is added as follows:

if v < B.peek():

    B.add(v)

    if B.size - 2*A.size >= 3:

        A.add(B.pull())

else:

    A.add(v)

    if B.size - 2*A.size < 0:

        B.add(A.pull())

The implementation for getting the n/3^th greatest value would be:

B.peek()

The time complexity for the above used methods is:

• size: O(1)
  


• peek: O(1)
  


• pull: O(logn)
  


• add: O(logn)
  

To maintain the overall maximum is an easy task. The heaps only serve for keeping track of the n/3^th greatest value.