Struttura dei dati per estrarre mediana e 2 ° elemento più piccolo O (LGN)

Question

Ho bisogno di trovare una struttura dati che soddisfa questi requisiti:

• può costruire da un elenco di n elementi nel tempo O (n)
• inserendo un elemento prende O (LGN)
• estraendo la mediana prende O (LGN)
• estrarre l'elemento più piccolo 2a prende O (LGN)

Per i primi tre r equient, questo funziona: mantieni n/2 gli oggetti più piccoli in un heap massimo e il n/2 il più grande in un heap minimo. Le radici di quei cumuli saranno la mediana inferiore/superiore.

Ma sono bloccato con il 4 ° requisito. Qualche idea?

Answer 1

Mantiene gli n/2 elementi più grandi in un heap minimo. Per gli articoli più piccoli n/2, mantenere una coppia di heap max e min. Gli heap in questa coppia sono aumentati con l'indice dello stesso elemento nell'heap accoppiato, in modo che qualsiasi modifica dell'heap aggiorni gli indici nell'heap accoppiato per tutti gli elementi spostati.

spiegazioni mucchio appaiati

Entrambi i cumuli contengono esattamente lo stesso insieme di elementi. Insieme a ciascun elemento c'è un campo indice aggiuntivo. Quando l'heap viene modificato, alcuni elementi potrebbero cambiare posizione. Se un articolo viene spostato dall'indice x all'indice , l'elemento corrispondente nell'heap associato deve essere notificato. Questo articolo corrispondente si trova facilmente nell'heap accoppiato con il campo dell'indice dell'oggetto spostato. E il contenuto del campo indice dell'articolo corrispondente viene modificato da x a . Ciò consente a tutti gli elementi heap di sapere esattamente dove si trovano le loro coppie. Mantenere gli elementi corrispondenti in entrambi gli heap in-sync consente (mentre si estrae l'elemento più grande dall'heap massimo o il secondo più piccolo dall'heap min) estrarre l'elemento corrispondente dall'heap associato. E mantenere i cumuli in-sync non aumenta nessuno dei requisiti di complessità.