Struttura dei dati per estrarre la mediana e il 2 ° elemento più piccolo in O (lgn) - strutture dati

Devo trovare una struttura di dati che soddisfi questi requisiti:

• può costruirlo da un elenco di n elementi in O (n)
• l'inserimento di un elemento richiede O (lgn)
• l'estrazione della mediana richiede O (lgn)
• l'estrazione del secondo elemento più piccolo richiede O (lgn)

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

Ma sono bloccato con il quarto requisito. Qualche idea?

risposte:

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

Spiegazioni heap accoppiate

Entrambi i cumuli contengono esattamente lo stesso insieme di elementi. Insieme a ciascun elemento è presente un campo indice aggiuntivo. Quando l'heap viene modificato, alcuni oggetti possono cambiare il loro posto. Se un elemento viene spostato dall'indice x indicizzare y, l'elemento corrispondente nell'heap associato deve esserenotificato. Questo elemento corrispondente si trova facilmente nell'heap accoppiato con il campo indice dell'oggetto spostato. Il contenuto del campo indice dell'oggetto corrispondente viene modificato da x a y. Ciò consente a tutti gli elementi heap di sapere esattamentedove si trovano le loro coppie. Mantenere sincronizzati gli elementi corrispondenti in entrambi gli heap consente (mentre si estrae l'elemento più grande dall'heap massimo o il 2 ° elemento più piccolo dall'heap minimo) estrarre l'elemento corrispondente dall'heap associato. E mantenere i cumuli in sincronia non aumenta nessuno dei requisiti di complessità.