Отслеживание медианы расширяющегося массива

Question

Вопрос об интервью:

Отредактировано ниже Вам дан массив.Вы делаете из него 2 кучи, одну кучи и другую кучи.Теперь найдите медиану массива, используя эти 2 предоставленные кучи за время O (nlog n).

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

Решение Эту проблему можно решить, используя 2 кучи, и к медиане всегда можно получить доступ в O (1) раз.

Answer 1

Вот как вы используете обе кучи. Обратите внимание, что я предполагаю, что вы не знаете количество элементов, и именно поэтому мы должны выталкивать, пока не извлечем что-то из минимальной кучи, которое больше или равно тому, что мы извлекаем из максимальной кучи. Обратите внимание, что мы возвращаем среднее значение, потому что в случае набора, подобного {1, 2, 3, 4}, медиана на самом деле равна 2.5 (среднее из двух «средних» значений). Я предполагаю double в качестве типа значения, но это может быть что угодно. Здесь:

double min = minheap.pop();
double max = maxheap.pop();
while(min < max) {
    min = minheap.pop();
    max = maxheap.pop();
}

return (min + max) / 2;

Поскольку всплывающее окно равно O(log n), и нам нужно выдвинуть O(n / 2) значения, это O(n log n).

Answer 2

Работающая реализация в Java, использующая 2 кучи, O (n log n).В любое время я сохраняю баланс между двумя кучами (т.е. они отличаются не более чем на 1, если мы ввели n элементов, таких что n% 2 == 1).Получение медианы - это O (1).Добавление нового элемента - O (log n).

public class MedianOfStream {

    private int count;
    private PriorityQueue<Integer> highs, lows;

    public MedianOfStream() {
        highs = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            @Override
            public int compare(Integer arg0, Integer arg1) {
                return arg0.compareTo(arg1);
            }
        });
        lows = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            @Override
            public int compare(Integer arg0, Integer arg1) {
                return arg1.compareTo(arg0);
            }
        });
    }

    private int getMedian() {
        if (count == 0)
            return 0;
        if (lows.size() == highs.size()) {
            return (lows.peek() + highs.peek()) / 2;
        } else if (lows.size() < highs.size()) {
            return highs.peek();
        }
        return lows.peek();
    }

    private void swap(){
        int h = highs.poll();
        int l = lows.poll();
        highs.add(l);
        lows.add(h);
    }

    public int updateMedian(int n) {
        count++;

        if (count == 1)
            lows.add(n);

        else if (count==2) {
            highs.add(n);
            if(highs.peek()<lows.peek()) {
                swap(); // O(log n)
            }
        }

        else {
            if (n > highs.peek()) {
                lows.add(highs.poll()); // O(log n)
                highs.add(n); // O(log n)
            } else {
                highs.add(lows.poll()); // O(log n)
                lows.add(n); // O(log n)
            }
            if(highs.peek()<lows.peek()) {
                swap(); // O(log n)
            }
        }

        // if we added an even # of items,
        // the heaps must be exactly the same size,
        // otherwise we tolerate a 1-off difference

        if (Math.abs(lows.size() - highs.size()) > (count % 2)) {
            if (lows.size() < highs.size()) {
                lows.add(highs.poll()); // O(log n)
            } else {
                highs.add(lows.poll()); // O(log n)
            }
        }

        return getMedian(); // O(1)
    }
}

Answer 3

Выгрузка из кучи - это операция O (log N), поэтому вы можете достичь O (N log N), извлекая половину элементов из одной из куч и принимая последнее вытолкнутое значение (вам придется обрабатывать ребро случаев). Это не использует в своих интересах другую кучу все же.

Вы можете достичь O (N), используя алгоритм выбора , но постоянный коэффициент очень высок. Первое предложение, вероятно, лучше, если у вас уже есть куча.

Answer 4

JavaScript-решение с использованием двух куч:

function addNewNumber(minHeap, maxHeap, randomNumber) {
  if (maxHeap.size() === minHeap.size()) {
    if (minHeap.peek() && randomNumber > minHeap.peek()) {
      maxHeap.insert(minHeap.remove());
      minHeap.insert(randomNumber);
    } else {
      maxHeap.insert(randomNumber);
    }
  } else {
    if (randomNumber < maxHeap.peek()) {
      minHeap.insert(maxHeap.remove());
      maxHeap.insert(randomNumber);
    } else {
      minHeap.insert(randomNumber);
    }
  }
}

function getMedian(minHeap, maxHeap) {
  if (!maxHeap.size()) {
    return 0;
  }
  if (minHeap.size() === maxHeap.size()) {
    return (minHeap.peek() + maxHeap.peek()) / 2;
  } else {
    return maxHeap.peek();
  }
}