Trovare la mediana - 2#4074

Trovare la mediana - 2 (Editoriale)

Modelliamo la soluzione del problema utilizzando un array lineare. Ad ogni passo memorizzeremo in esso i numeri in arrivo in forma ordinata. La posizione per l'inserimento di un nuovo elemento verrà trovata mediante ricerca binaria. Tuttavia, l'operazione di inserimento stessa (ad esempio, se l'array è implementato utilizzando la struttura dati $v ec t or$ ) viene eseguita in tempo lineare. Pertanto, la soluzione complessiva con complessità temporale $O (n^{2})$ O(n^2) non rientrerà nel limite di tempo.

Dichiariamo due heap: uno — per memorizzare il minimo ( $min$ -heap), l'altro — per memorizzare il massimo ( $ma x$ -heap). Organizziamo il loro funzionamento in modo che siano soddisfatte le seguenti condizioni:

qualsiasi elemento del $ma x$ -heap sia minore di qualsiasi elemento del $min$ -heap (i numeri più piccoli sono memorizzati nel $ma x$ -heap, e quelli più grandi nel $min$ -heap);
le dimensioni degli heap siano uguali. Se il numero totale di elementi è dispari, il $min$ -heap deve contenere un elemento in più rispetto al $ma x$ -heap.

Quando si aggiunge un nuovo elemento, lo inseriamo nel $min$ -heap se non è minore dell'elemento minimo di questo heap; altrimenti — nel $ma x$ -heap. Successivamente eseguiamo il bilanciamento degli heap per mantenere le proprietà sopra indicate:

Se la dimensione del $ma x$ -heap supera la dimensione del $min$ -heap, trasferiamo l'elemento massimo dal $ma x$ -heap al $min$ -heap.
Se la dimensione del $min$ -heap supera di più di un elemento la dimensione del $ma x$ -heap, trasferiamo l'elemento minimo dal $min$ -heap al $ma x$ -heap.

La mediana della sequenza corrente viene determinata come segue:

se il numero di numeri è dispari, la mediana è l'elemento minimo del $min$ -heap;
se il numero di numeri è pari, la mediana è uguale alla media aritmetica dell'elemento minimo del $min$ -heap e dell'elemento massimo del $ma x$ -heap.

L'inserimento di un elemento nell'heap e il successivo bilanciamento vengono eseguiti in tempo $O (l o g_{2} n)$ O(log_2n). Pertanto, il tempo totale di esecuzione dell'algoritmo è $O (n l o g_{2} n)$ O(nlog_2n).

Esempio

Consideriamo il processo di calcolo della mediana con l'arrivo sequenziale dei numeri. Per chiarezza, supporremo che dopo l'aggiunta di ogni nuovo numero la sequenza venga ordinata. Sotto ogni sequenza è indicato il valore corrispondente della mediana.

Dopo aver elaborato tutti gli elementi dell'esempio, lo stato degli heap sarà il seguente:

Poiché il numero di elementi è dispari, la mediana è uguale all'elemento minimo del $min$ -heap, cioè $4$ .

Supponiamo che arrivi successivamente il numero $35$ . Poiché non è minore dell'elemento minimo del $min$ -heap, lo aggiungiamo al $min$ -heap. Dopo di che la dimensione del $min$ -heap risulterà maggiore di due elementi rispetto alla dimensione del $ma x$ -heap, quindi è necessario eseguire il bilanciamento: trasferire l'elemento minimo del $min$ -heap ( $4$ ) nel $ma x$ -heap. In altre parole, rimuoviamo $4$ dal $min$ -heap e lo aggiungiamo al $ma x$ -heap.

Ora il numero totale di elementi nell'array è pari, quindi la mediana viene determinata come la media aritmetica dell'elemento minimo del $min$ -heap ( $35$ ) e dell'elemento massimo del $ma x$ -heap ( $4$ ), cioè $(35 + 4) /2 = 19$ (35 + 4) / 2 = 19. Nel problema è richiesto di stampare solo la parte intera della mediana.

Implementazione dell'algoritmo

Dichiariamo il $min$ -heap $m M in H e a p$ mMinHeap e il $ma x$ -heap $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;

Inizializziamo gli heap. Nella variabile $c$ memorizzeremo il numero di numeri ricevuti in ingresso. Per comodità, inizializziamo gli heap con elementi fittizi.

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

Elaboriamo il numero successivo.

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

A seconda del valore di $n$ , lo inseriamo in uno degli heap.

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

Se la dimensione del $ma x$ -heap supera la dimensione del $min$ -heap, oppure la dimensione del $min$ -heap supera di più di un elemento la dimensione del $ma x$ -heap, eseguiamo il bilanciamento.

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

Trasferiamo l'elemento massimo del $ma x$ -heap nel $min$ -heap.

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

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

Trasferiamo l'elemento minimo del $min$ -heap nel $ma x$ -heap.

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

A seconda della parità del numero di elementi nell'array, stampiamo il valore della mediana.

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