Знайти медіану - 2#4074

Знайти медіану - 2 (Розбір)

Промоделюємо розв'язання задачі за допомогою лінійного масиву. На кожному кроці будемо зберігати в ньому числа, що надходять, у відсортованому вигляді. Позицію для вставки нового елемента будемо знаходити за допомогою бінарного пошуку. Однак сама операція вставки (наприклад, якщо масив реалізований з використанням структури даних $v ec t or$ ) виконується за лінійний час. Таким чином, загальне рішення з часовою складністю $O (n^{2})$ O(n^2) не вкладеться в обмеження за часом.

Оголосимо дві купи: одну — для зберігання мінімуму ( $min$ -купа), іншу — для зберігання максимуму ( $ma x$ -купа). Організуємо їхню роботу так, щоб виконувалися такі умови:

будь-який елемент $ma x$ -купи був меншим за будь-який елемент $min$ -купи (менші числа зберігаються в $ma x$ -купі, а більші в $min$ -купі);
розміри куп були рівні. Якщо загальна кількість елементів непарна, $min$ -купа повинна містити на один елемент більше, ніж $ma x$ -купа.

При додаванні нового елемента поміщаємо його в $min$ -купу, якщо він не менший за мінімальний елемент цієї купи; в іншому випадку — в $ma x$ -купу. Після цього виконуємо балансування куп, щоб зберегти зазначені вище властивості:

Якщо розмір $ma x$ -купи перевищує розмір $min$ -купи, переносимо найбільший елемент з $ma x$ -купи в $min$ -купу.
Якщо розмір $min$ -купи більш ніж на один елемент перевищує розмір $ma x$ -купи, переносимо найменший елемент з $min$ -купи в $ma x$ -купу.

Медіана поточної послідовності визначається наступним чином:

якщо кількість чисел непарна, медіаною є найменший елемент $min$ -купи;
якщо кількість чисел парна, медіана дорівнює середньому арифметичному найменшого елемента $min$ -купи та найбільшого елемента $ma x$ -купи.

Вставка елемента в купу та подальше балансування виконуються за час $O (l o g_{2} n)$ O(log_2n). Таким чином, загальний час роботи алгоритму становить $O (n l o g_{2} n)$ O(nlog_2n).

Приклад

Розглянемо процес обчислення медіани при послідовному надходженні чисел. Для наочності будемо вважати, що після додавання кожного нового числа послідовність впорядковується. Під кожною послідовністю вказано відповідне значення медіани.

Після обробки всіх елементів прикладу стан куп буде наступним:

Оскільки кількість елементів непарна, медіана дорівнює найменшому елементу $min$ -купи, тобто $4$ .

Нехай наступним надходить число $35$ . Оскільки воно не менше за мінімальний елемент $min$ -купи, додамо його в $min$ -купу. Після цього розмір $min$ -купи виявиться на два елементи більшим за розмір $ma x$ -купи, тому необхідно виконати балансування: перенести найменший елемент $min$ -купи ( $4$ ) в $ma x$ -купу. Іншими словами, видаляємо $4$ з $min$ -купи і додаємо його в $ma x$ -купу.

Тепер загальна кількість елементів у масиві парна, тому медіана визначається як середнє арифметичне найменшого елемента $min$ -купи ( $35$ ) та найбільшого елемента $ma x$ -купи ( $4$ ), тобто $(35 + 4) /2 = 19$ (35 + 4) / 2 = 19. У задачі потрібно виводити лише цілу частину медіани.

Реалізація алгоритму

Оголосимо $min$ -купу $m M in H e a p$ mMinHeap та $ma x$ -купу $m M a x H e a p$ mMaxHeap.

priority_queue<int, vector<int>, greater<int> > mMinHeap;
priority_queue<int, vector<int>, less<int> > mMaxHeap;

Ініціалізуємо купи. У змінній $c$ будемо зберігати кількість чисел, що надійшли на вхід. Для зручності ініціалізуємо купи фіктивними елементами.

mMaxHeap.push(-MAX); mMinHeap.push(MAX);
c = 1;

Обробляємо чергове число.

while(scanf("%d",&n) == 1) 
{

Залежно від значення $n$ поміщаємо його в одну з куп.

  if (n >= mMinHeap.top()) mMinHeap.push(n);
  else mMaxHeap.push(n);

Якщо розмір $ma x$ -купи перевищує розмір $min$ -купи або розмір $min$ -купи більш ніж на один елемент перевищує розмір $ma x$ -купи, виконуємо балансування.

  if(mMaxHeap.size() > mMinHeap.size())
  {

Найбільший елемент $ma x$ -купи переносимо в $min$ -купу.

    mMinHeap.push(mMaxHeap.top());
    mMaxHeap.pop();
  } else

  if(mMaxHeap.size() + 1 < mMinHeap.size())
  {

Найменший елемент $min$ -купи переносимо в $ma x$ -купу.

    mMaxHeap.push(mMinHeap.top());
    mMinHeap.pop();
  }

Залежно від парності кількості елементів у масиві виводимо значення медіани.

  if (c % 2) printf("%d\n",mMinHeap.top()); 
  else printf("%d\n",(mMinHeap.top() + mMaxHeap.top())/2); 
  c++;
}