Estructura de datos para extraer la mediana y el segundo elemento más pequeño en O (LGN)

Question

Tengo que encontrar una estructura de datos que cumple con estos requisitos:

• puede construir a partir de una lista de n elementos en O (n)
• se inserta un elemento toma O (LGN)
• extracción de la mediana toma O (LGN)
• extraer el segundo elemento más pequeño toma O (LGN)

para los tres primeros r Equivalentes, esto funciona: mantenga los n/2 elementos más pequeños en un montón máximo y el n/2 más grande en un montón mínimo. Las raíces de esos montones serán la mediana inferior/superior.

Pero estoy atascado con el cuarto requisito. ¿Algunas ideas?

Answer 1

Mantenga los n/2 elementos más grandes en un montón mínimo. Para los n/2 elementos más pequeños, mantenga un par de montones máximo y mínimo. Los montículos en este par se aumentan con el índice del mismo elemento en el montón vinculado, de modo que cualquier modificación del montón actualiza los índices en el montón emparejado para todos los elementos movidos.

apareadas explicaciones montón

Ambos montones contienen exactamente el mismo conjunto de elementos. Junto con cada elemento, hay un campo de índice adicional. Cuando se modifica el montón, algunos elementos pueden cambiar sus lugares. Si un elemento se mueve desde el índice x al índice y, debe notificarse el artículo correspondiente en el montón emparejado. Este elemento correspondiente se ubica fácilmente en un montón emparejado con el campo índice del elemento movido. Y el contenido del campo de índice del artículo correspondiente se cambia de x a y. Esto permite que todos los elementos del montón conozcan exactamente dónde están ubicados sus pares. Mantener los elementos correspondientes en ambos montones sincronizados permite (al extraer el elemento más grande del montón máximo o el segundo elemento más pequeño del montón mínimo) extraer el elemento correspondiente del montón emparejado. Y mantener montones sincronizados no aumenta ninguno de los requisitos de complejidad.