Ho letto una domanda e sto cercando suggerimenti su come risolverlo:
Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?
Ci sono due strutture dati in grado di risolvere il problema. Uno è l'albero binario bilanciato, l'altro è due cumuli che tengono traccia della metà più grande e della metà più piccola degli elementi.
Penso che queste due soluzioni abbiano lo stesso tempo di esecuzione di O(n lg n) , ma non sono sicuro del mio giudizio.
Qual è il modo migliore per tenere traccia della mediana?
Il mio tentativo:
In questa domanda, penso che un mucchio sia il modo migliore per tenere traccia della mediana. Ci sono due heap, il grande heap e il piccolo heap, che non devono essere sequenziali. Innanzitutto, calcoliamo il valore medio degli elementi nella matrice. Se l'elemento è inferiore al valore medio, inseriamo il num nel piccolo heap. Al contrario, mettiamo il numero sul grande mucchio. Se il numero del grande heap è uguale al numero del piccolo heap, il più grande nel piccolo heap e il più piccolo nel grande heap sono la mediana. Se i due heap hanno dimensioni diverse, inseriamo l'elemento radice dall'heap con dimensioni maggiori e lo inseriamo nella radice dell'heap di dimensioni più piccole. Per l'heap grande, l'elemento radice è il più piccolo e, per l'heap piccolo, l'elemento radice è il più grande. In questo modo, se i due heap hanno la stessa dimensione o una differenza digitale, troviamo il supporto nella radice.
Penso che questa soluzione abbia il tempo di esecuzione come O (m * n), m indica le volte in cui aggiustiamo gli heap di squilibrio.
È questo il modo migliore per tenere traccia della mediana?