оптимизировать добавление номера в очередь для медианы из потока чисел

Question

Мне недавно задали этот вопрос в интервью, чтобы найти медиану из потока данных чисел, и я смог найти решение Priority Queue, как показано ниже:

public class MedianFinder {
  private final PriorityQueue<Long> min = new PriorityQueue<>();
  private final PriorityQueue<Long> max = new PriorityQueue<>(Collections.reverseOrder());

  public void addNum(long num) {
    max.offer(num);
    min.offer(max.poll());
    if (max.size() < min.size()) {
      max.offer(min.poll());
    }
  }

  public double findMedian() {
    if (max.size() == min.size())
      return (max.peek() + min.peek()) / 2.0;
    else
      return max.peek();
  }
}

Теперь интервьюер хотел меняоптимизировать метод addNum, потому что в нем много операций O (log n) (около 5), и он хотел посмотреть, сможем ли мы еще оптимизировать его, чтобы у нас было меньше операций O (log n)?Есть ли что-то, что мы можем сделать здесь, чтобы оптимизировать метод addNum?

Answer 1

Это может уменьшить среднее количество вызовов offer с 2,5 до 1,5 и poll вызовов с 1,5 до 0,5. Общее сокращение среднего числа операций O (log n) с 4 до 2.

public void addNum(long num) {
    if(!max.isEmpty() )
    {
        if(max.size() == min.size())
        {
            if(num > max.peek())
            {
                min.offer(num);
                max.offer(min.poll());
            }
            else
            {
                max.offer(num);
            }
        }
        else
        {
            if(num > max.peek())
            {
                min.offer(num);
            }
            else
            {
                max.offer(num);
                min.offer(max.poll());
            }
        }
    }
    else
    {
        max.offer(num);
    }
}

Более компактная версия (та же логика)

public void addNum(long num) {
    if(!max.isEmpty())
    {
        (num > max.peek() ? min : max).offer(num);
        if(min.size() > max.size())
        {
            max.offer(min.poll());
        }
        else if(max.size() - min.size() > 1)
        {
            min.offer(max.poll());
        }
    }
    else
    {
        max.offer(num);
    }
}