Рубрики
Без рубрики

Медиана потока целых чисел с использованием кучи в Java

Узнайте, как вычислить медиану потока целых чисел с помощью кучи

Автор оригинала: Priyank Srivastava.

1. Обзор

В этом уроке мы узнаем, как вычислить медиану потока целых чисел.

Мы продолжим, изложив проблему с примерами, затем проанализируем проблему и, наконец, реализуем несколько решений на Java.

2. Постановка проблемы

Срединный является средним значением упорядоченного набора данных. Для набора целых чисел существует столько же элементов, меньших медианы, сколько и больше.

В упорядоченном наборе:

  • нечетное число целых чисел, средний элемент – медиана-в упорядоченном множестве { 5, 7, 10 } , медиана равна 7
  • четное число целых чисел, среднего элемента нет; медиана вычисляется как среднее значение двух средних элементов – в упорядоченном наборе {5, 7, 8, 10} , медиана равна (7 + 8)/.5

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

Давайте формализуем постановку задачи. Учитывая входные данные потока целых чисел, мы должны разработать класс, который выполняет следующие две задачи для каждого целого числа, которое мы читаем:

  1. Добавьте целое число к набору целых чисел
  2. Найдите медиану целых чисел, прочитанных до сих пор

Например:

add 5         // sorted-set = { 5 }, size = 1
get median -> 5

add 7         // sorted-set = { 5, 7 }, size = 2 
get median -> (5 + 7) / 2 = 6

add 10        // sorted-set = { 5, 7, 10 }, size = 3 
get median -> 7

add 8         // sorted-set = { 5, 7, 8, 10 }, size = 4 
get median -> (7 + 8) / 2 = 7.5
..

Хотя поток не является конечным, мы можем предположить, что можем хранить все элементы потока в памяти одновременно.

Мы можем представить наши задачи в виде следующих операций в коде:

void add(int num);

double getMedian();

3. Наивный Подход

3.1. Сортированный список

Давайте начнем с простой идеи – мы можем вычислить медиану отсортированного списка целых чисел , обратившись к среднему элементу или двум средним элементам списка по индексу. Временная сложность операции getMedian равна O(1) .

При добавлении нового целого числа мы должны определить его правильное положение в списке таким образом, чтобы список оставался отсортированным. Эта операция может быть выполнена за O(n) время, где n – размер списка . Таким образом, общая стоимость добавления нового элемента в список и вычисления новой медианы составляет O(n) .

3.2. Совершенствование Наивного подхода

Операция add выполняется в линейном времени, что не является оптимальным. Давайте попробуем рассмотреть это в этом разделе.

Мы можем разделить список на два отсортированных списка – меньшая половина целых чисел, отсортированных в порядке убывания, и большая половина целых чисел в порядке возрастания . Мы можем добавить новое целое число в соответствующую половину, чтобы размер списков отличался не более чем на 1:

if element is smaller than min. element of larger half:
    insert into smaller half at appropriate index
    if smaller half is much bigger than larger half:
        remove max. element of smaller half and insert at the beginning of larger half (rebalance)
else
    insert into larger half at appropriate index:
    if larger half is much bigger than smaller half:
        remove min. element of larger half and insert at the beginning of smaller half (rebalance)

Теперь мы можем вычислить медиану:

if lists contain equal number of elements:
    median = (max. element of smaller half + min. element of larger half) / 2
else if smaller half contains more elements:
    median = max. element of smaller half
else if larger half contains more elements:
    median = min. element of larger half

Хотя мы только улучшили временную сложность операции add на некоторый постоянный коэффициент, мы добились прогресса.

Давайте проанализируем элементы, к которым мы обращаемся в двух отсортированных списках |. Мы потенциально получаем доступ к каждому элементу, перемещая их во время операции (сортировка) add . Что еще более важно, мы получаем доступ к минимуму и максимуму (экстремумам) большей и меньшей половин соответственно во время операции add для перебалансировки и во время операции getMedian .

Мы видим, что экстремумы являются первыми элементами соответствующих списков . Итак, мы должны оптимизировать доступ к элементу в индексе 0 для каждой половины для улучшения общего времени выполнения операции добавить .

4. Подход, основанный на куче

Давайте уточним наше понимание проблемы, применив то, что мы узнали из нашего наивного подхода:

  1. Мы должны получить минимальный/максимальный элемент набора данных за O(1) время
  2. Элементы не должны храниться в отсортированном порядке до тех пор, пока мы можем эффективно получить минимальный/максимальный элемент
  3. Нам нужно найти подход для добавления элемента в наш набор данных, который стоит меньше, чем O(n) время

Далее мы рассмотрим структуру данных кучи, которая помогает нам эффективно достигать наших целей.

4.1. Структура данных Кучи

Куча – это структура данных , которая обычно реализуется с помощью массива, но может рассматриваться как двоичное дерево .

Кучи ограничены свойством кучи:

4.1.1. Свойство Max–heap

(Дочерний) узел не может иметь значение, большее, чем значение его родителя. Следовательно, в max-heap корневой узел всегда имеет наибольшее значение.

4.1.2. Свойство Min–heap

(Родительский) узел не может иметь значения больше, чем у его дочерних узлов. Таким образом, в min-heap корневой узел всегда имеет наименьшее значение.

В Java класс PriorityQueue представляет собой кучу. Давайте перейдем к нашему первому решению с использованием кучи.

4.2. Первое решение

Давайте заменим списки в нашем наивном подходе двумя кучами:

  • Минимальная куча, содержащая большую половину элементов, с минимальным элементом в корне
  • Максимальная куча, содержащая меньшую половину элементов, с максимальным элементом в корне

Теперь мы можем добавить входящее целое число к соответствующей половине, сравнив его с корнем минимальной кучи. Далее, если после вставки размер одной кучи отличается от размера другой кучи более чем на 1, мы можем перебалансировать кучи, сохраняя таким образом разницу в размере не более 1:

if size(minHeap) > size(maxHeap) + 1:
    remove root element of minHeap, insert into maxHeap
if size(maxHeap) > size(minHeap) + 1:
    remove root element of maxHeap, insert into minHeap

При таком подходе мы можем вычислить медиану как среднее значение корневых элементов обеих куч, если размер двух куч одинаков. В противном случае корневым элементом кучи с большим количеством элементов является медиана .

Мы будем использовать класс PriorityQueue для представления кучи. Свойство кучи по умолчанию для Приоритетной очереди имеет значение min-heap. Мы можем создать максимальную кучу, используя Comparator.reverserOrder , который использует обратный естественный порядок:

class MedianOfIntegerStream {

    private Queue minHeap, maxHeap;

    MedianOfIntegerStream() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }

    void add(int num) {
        if (!minHeap.isEmpty() && num < minHeap.peek()) {
            maxHeap.offer(num);
            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
            }
        } else {
            minHeap.offer(num);
            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            }
        }
    }

    double getMedian() {
        int median;
        if (minHeap.size() < maxHeap.size()) {
            median = maxHeap.peek();
        } else if (minHeap.size() > maxHeap.size()) {
            median = minHeap.peek();
        } else {
            median = (minHeap.peek() + maxHeap.peek()) / 2; 
        }
        return median;
    }
}

Прежде чем мы проанализируем время выполнения нашего кода, давайте посмотрим на временную сложность операций кучи, которые мы использовали:

find-min/find-max        O(1)    

delete-min/delete-max    O(log n)

insert                   O(log n)

Таким образом, операция getMedian может быть выполнена за O(1) время, поскольку для этого требуются только функции find-min и find-max . Временная сложность операции add составляет O(log n) – три insert |/delete вызовы, каждый из которых требует O(log n) времени.

4.3. Инвариантное решение Размера Кучи

В нашем предыдущем подходе мы сравнивали каждый новый элемент с корневыми элементами куч. Давайте рассмотрим другой подход с использованием кучи, в котором мы можем использовать свойство кучи для добавления нового элемента в соответствующую половину.

Как и в предыдущем решении, мы начинаем с двух куч – минимальной и максимальной. Далее введем условие: размер максимальной кучи должен быть (n/2) в любое время, в то время как размер минимальной кучи может быть (n/2) или (n/2) + 1 , в зависимости от общего количества элементов в двух кучах . Другими словами, мы можем позволить только минимальной куче иметь дополнительный элемент, когда общее количество элементов нечетно.

С нашим инвариантом размера кучи мы можем вычислить медиану как среднее значение корневых элементов обеих куч, если размеры обеих куч равны (n/2) . В противном случае корневым элементом минимальной кучи является медиана .

Когда мы добавляем новое целое число, у нас есть два сценария:

1. Total no. of existing elements is even
   size(min-heap) == size(max-heap) == (n / 2)

2. Total no. of existing elements is odd
   size(max-heap) == (n / 2)
   size(min-heap) == (n / 2) + 1

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

Перебалансировка выполняется путем перемещения самого большого элемента из максимальной кучи в минимальную кучу или путем перемещения самого маленького элемента из минимальной кучи в максимальную кучу. Таким образом, хотя мы не сравниваем новое целое число перед добавлением его в кучу, последующая перебалансировка гарантирует, что мы соблюдаем базовый инвариант меньших и больших половин .

Давайте реализуем наше решение на Java, используя Очереди приоритетов :

class MedianOfIntegerStream {

    private Queue minHeap, maxHeap;

    MedianOfIntegerStream() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }

    void add(int num) {
        if (minHeap.size() == maxHeap.size()) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

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

Временные сложности наших операций остаются неизменными : getMedian затраты O(1) время, в то время как add выполняется во времени O(log n) с точно таким же количеством операций.

Оба решения на основе кучи предлагают схожие пространственные и временные сложности. Хотя второе решение является умным и имеет более чистую реализацию, подход не является интуитивным. С другой стороны, первое решение естественно следует нашей интуиции, и легче рассуждать о правильности его добавления операции.

5. Заключение

В этом уроке мы узнали, как вычислить медиану потока целых чисел. Мы оценили несколько подходов и реализовали несколько различных решений в Java, используя Очередь приоритетов .

Как обычно, исходный код для всех примеров доступен на GitHub .