Эффективно найти медианное значение случайной последовательности

Question

Числа генерируются случайным образом и передаются методу. Напишите программу для поиска и поддержания значения медианы при создании новых значений.

Размеры кучи могут быть одинаковыми, или у кучи ниже есть один дополнительный.

private Comparator<Integer> maxHeapComparator, minHeapComparator;
private PriorityQueue<Integer> maxHeap, minHeap;

public void addNewNumber(int randomNumber) {
  if (maxHeap.size() == minHeap.size()) {
    if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) {
      maxHeap.offer(minHeap.poll());
      minHeap.offer(randomNumber);
    } else {
      maxHeap.offer(randomNumber);
    }
  }
  else {  // why the following block is correct? 
    // I think it may create unbalanced heap size
    if(randomNumber < maxHeap.peek()) {
      minHeap.offer(maxHeap.poll());
      maxHeap.offer(randomNumber);
    }
    else {
      minHeap.offer(randomNumber);
    }
  }
}

public static double getMedian() {
  if (maxHeap.isEmpty()) return minHeap.peek();
  else if (minHeap.isEmpty()) return maxHeap.peek();

  if (maxHeap.size() == minHeap.size()) {
    return (minHeap.peek() + maxHeap.peek()) / 2;
  } else if (maxHeap.size() > minHeap.size()) {
    return maxHeap.peek();
  } else {
    return minHeap.peek();
  }
}

Предположим, что решение верное, тогда я не понимаю, почему блок кода (см. Мои комментарии) может поддерживать баланс размера кучи. Другими словами, разница в размерах двух куч составляет 0 или 1.

Let us see an example, given a sequence 1, 2, 3, 4, 5
The first random number is **1**
    max-heap: 1
    min-heap:

The second random number is **2**
    max-heap: 1
    min-heap: 2

The third random number is **3**
    max-heap: 1 2
    min-heap: 3 4

The fourth random number is **4**
    max-heap: 1 2 3
    min-heap: 4 5

Спасибо

Answer 1

После выполнения данной последовательности

max-heap : 1, 2, 3
min-heap : 4, 5

, поскольку размер max-heap равен> min-heap, в качестве медианы возвращается 3.

max-heap хранит левую половину элементовприблизительно и min-heap хранит правую половину последовательности приблизительно.

этот код смещен в сторону левой половины, то есть max-heap.

Я не понимаю, почему этот код неверен.