Mediana del flusso di numeri interi utilizzando Heap in Java

1. Panoramica

In questo tutorial impareremo come calcolare la mediana di un flusso di numeri interi.

Procederemo affermando il problema con esempi, quindi analizzeremo il problema e infine implementeremo diverse soluzioni in Java.

2. Dichiarazione del problema

La mediana è il valore medio di un set di dati ordinato. Per un insieme di numeri interi, ci sono tanti elementi minori della mediana quanto maggiori.

In un set ordinato di:

  • numero dispari di interi, l'elemento centrale è la mediana - nell'insieme ordinato {5, 7, 10} , la mediana è 7
  • numero pari di numeri interi, non c'è elemento centrale; la mediana è calcolata come la media dei due elementi intermedi - nell'insieme ordinato {5, 7, 8, 10} , la mediana è (7 + 8) / 2 = 7.5

Ora, supponiamo che invece di un insieme finito, stiamo leggendo interi da un flusso di dati. Possiamo definire la mediana di un flusso di interi come la mediana dell'insieme di interi letti fino a quel momento .

Formalizziamo la dichiarazione del problema. Dato un input di un flusso di numeri interi, dobbiamo progettare una classe che esegue le seguenti due attività per ogni numero intero che leggiamo:

  1. Aggiungi il numero intero al set di numeri interi
  2. Trova la mediana degli interi letti finora

Per esempio:

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 .. 

Sebbene il flusso non sia finito, possiamo presumere di poter conservare tutti gli elementi del flusso in memoria contemporaneamente.

Possiamo rappresentare le nostre attività come le seguenti operazioni nel codice:

void add(int num); double getMedian(); 

3. Approccio ingenuo

3.1. Elenco ordinato

Cominciamo con un'idea semplice: possiamo calcolare la mediana di un elenco ordinato di numeri interi accedendo all'elemento centrale o ai due elementi centrali dell'elenco , per indice. La complessità temporale dell'operazione getMedian è O (1) .

Durante l'aggiunta di un nuovo numero intero, dobbiamo determinare la sua posizione corretta nell'elenco in modo che l' elenco rimanga ordinato. Questa operazione può essere eseguita in tempo O (n) , dove n è la dimensione della lista . Quindi, il costo complessivo per aggiungere un nuovo elemento all'elenco e calcolare la nuova mediana è O (n) .

3.2. Migliorare l'approccio ingenuo

L' operazione di aggiunta viene eseguita in tempo lineare, il che non è ottimale. Proviamo ad affrontarlo in questa sezione.

Possiamo dividere l' elenco in due elenchi ordinati : la metà più piccola degli interi ordinati in ordine decrescente e la metà più grande degli interi in ordine crescente . Possiamo aggiungere un nuovo numero intero nella metà appropriata in modo che la dimensione delle liste differisca di 1, al massimo:

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) 

Ora possiamo calcolare la mediana:

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

Sebbene abbiamo solo migliorato la complessità temporale dell'operazione di aggiunta di qualche fattore costante, abbiamo compiuto progressi.

Analizziamo gli elementi a cui accediamo nei due elenchi ordinati . Potenzialmente accediamo a ogni elemento mentre li spostiamo durante l' operazione di aggiunta (ordinata) . Ancora più importante, accediamo rispettivamente al minimo e al massimo (estremi) delle metà più grande e più piccola, durante l' operazione di aggiunta per il riequilibrio e durante l' operazione getMedian .

Possiamo vedere che gli estremi sono i primi elementi delle rispettive liste . Quindi, dobbiamo ottimizzare per accedere all'elemento all'indice 0 per ogni metà per migliorare il tempo di esecuzione complessivo dell'operazione di aggiunta .

4. Approccio basato su heap

Affiniamo la nostra comprensione del problema, applicando ciò che abbiamo imparato dal nostro approccio ingenuo:

  1. Dobbiamo l'elemento minimo / massimo di un set di dati in O (1) tempo
  2. Gli elementi non devono essere tenuti in un ordine ordinato fintanto che possiamo ottenere l'elemento minimo / massimo in modo efficiente
  3. Dobbiamo trovare un approccio per aggiungere un elemento al nostro set di dati che costi meno di O (n) tempo

Successivamente, esamineremo la struttura dei dati di Heap che ci aiuta a raggiungere i nostri obiettivi in ​​modo efficiente.

4.1. Struttura dei dati dell'heap

L'heap è una struttura dati che di solito viene implementata con un array ma può essere considerata come un albero binario .

Gli heap sono vincolati dalla proprietà heap:

4.1.1. Max - proprietà heap

Un nodo (figlio) non può avere un valore maggiore di quello del suo genitore. Quindi, in un max-heap , il nodo radice ha sempre il valore più grande.

4.1.2. Min - proprietà heap

Un nodo (genitore) non può avere un valore maggiore di quello dei suoi figli. Pertanto, in un min-heap , il nodo radice ha sempre il valore più piccolo.

In Java, la classe PriorityQueue rappresenta un mucchio. Passiamo alla nostra prima soluzione utilizzando gli heap.

4.2. Prima soluzione

Sostituiamo le liste nel nostro approccio ingenuo con due cumuli:

  • Un min-heap che contiene la metà più grande degli elementi, con l'elemento minimo alla radice
  • Un max-heap che contiene la metà più piccola degli elementi, con l'elemento massimo alla radice

Ora possiamo aggiungere l'intero in entrata alla metà pertinente confrontandolo con la radice del min-heap. Successivamente, se dopo l'inserimento, la dimensione di un heap differisce da quella dell'altro heap di più di 1, possiamo ribilanciare gli heap, mantenendo così una differenza di dimensione al massimo 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

Con questo approccio, possiamo calcolare la mediana come media degli elementi radice di entrambi gli heap, se la dimensione dei due heap è uguale. In caso contrario, l' elemento radice dell'heap con più elementi è la mediana .

Useremo la classe PriorityQueue per rappresentare gli heap. La proprietà heap predefinita di PriorityQueue è min-heap. Possiamo creare un max-heap utilizzando un Comparator.reverserOrder che utilizza il contrario dell'ordine naturale:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (!minHeap.isEmpty() && num  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 = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

Prima di analizzare il tempo di esecuzione del nostro codice, diamo un'occhiata alla complessità temporale delle operazioni di heap che abbiamo utilizzato:

find-min/find-max O(1) delete-min/delete-max O(log n) insert O(log n) 

Quindi, l' operazione getMedian può essere eseguita in tempo O (1) poiché richiede solo le funzioni find-min e find-max . La complessità temporale dell'operazione di aggiunta è O (log n) : tre chiamate di inserimento / cancellazione ciascuna che richiede tempo O (log n) .

4.3. Soluzione invariante dimensione heap

Nel nostro approccio precedente, abbiamo confrontato ogni nuovo elemento con gli elementi radice degli heap. Esploriamo un altro approccio che utilizza l'heap in cui possiamo sfruttare la proprietà heap per aggiungere un nuovo elemento nella metà appropriata.

As we have done for our previous solution, we begin with two heaps – a min-heap and a max-heap. Next, let's introduce a condition: the size of the max-heap must be (n / 2) at all times, while the size of the min-heap can be either (n / 2) or (n / 2) + 1, depending on the total number of elements in the two heaps. In other words, we can allow only the min-heap to have an extra element, when the total number of elements is odd.

With our heap size invariant, we can compute the median as the average of the root elements of both heaps, if the sizes of both heaps are (n / 2). Otherwise, the root element of the min-heap is the median.

When we add a new integer, we have two scenarios:

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 

We can maintain the invariant by adding the new element to one of the heaps and rebalancing every time:

The rebalancing works by moving the largest element from the max-heap to the min-heap, or by moving the smallest element from the min-heap to the max-heap. This way, though we're not comparing the new integer before adding it to a heap, the subsequent rebalancing ensures that we honor the underlying invariant of smaller and larger halves.

Let's implement our solution in Java using PriorityQueues:

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; } }

The time complexities of our operations remain unchanged: getMedian costs O(1) time, while add runs in time O(log n) with exactly the same number of operations.

Entrambe le soluzioni basate su heap offrono complessità di spazio e tempo simili. Sebbene la seconda soluzione sia intelligente e abbia un'implementazione più pulita, l'approccio non è intuitivo. D'altra parte, la prima soluzione segue naturalmente la nostra intuizione, ed è più facile ragionare sulla correttezza della sua operazione di addizione .

5. Conclusione

In questo tutorial, abbiamo imparato come calcolare la mediana di un flusso di numeri interi. Abbiamo valutato alcuni approcci e implementato un paio di soluzioni diverse in Java utilizzando PriorityQueue .

Come al solito, il codice sorgente di tutti gli esempi è disponibile su GitHub.