Esta es una pregunta de la entrevista. Necesita diseñar una cola que contenga valores enteros y tenga una función getMedian() que devuelva el elemento mediano de la cola actual. Puedes usar O (n) espacio extra.diseñar una cola que admita la función getMedian
¿Puede getMedian() implementarse con complejidad de tiempo < O (n)?
Por ejemplo: Cuando la cola tiene los siguientes valores (2, 1, 2, 2, 6, 4, 2, 5) este método devuelve 2 y no elimina ese objeto.
La aplicación conocida por su problema es tan así:
Lo que hay que aplicar es de 2 montones, uno será un min-pila y la otra un máximo en heap.
También necesitará un número entero para indicarnos la cantidad de objetos en su cola.
Las restricciones para los montones son los siguientes:
1. El min-montón tendrán los objetos de mayor tamaño de la cola de
2. El max-montón tendrá los objetos más pequeños de la cola de
3. La max-heap tendrá el mismo u 1 objeto más que tu min-heap
De esta forma, si tienes un número impar de objetos, la mediana sería exactamente el máximo en tu montón máximo. Si tiene un número par de objetos, su mediana sería el promedio de ambas raíces de sus montones (máximo de montón máximo, mínimo de montón mínimo).
Es importante tener en cuenta que si sus montones se vuelven irregulares, por ejemplo, si "salta" de un cierto montón, tendrá que quitar del otro montón y moverlo. Pero eso no es un problema, ya que todo lo que necesita para enfrentar es la raíz de sus montones y nada más.
La complejidad del tiempo de getMedian se convierte en O (1)
acaba de encontrar un artículo sobre el tema: link
respuesta al comentario
El max-heap tiene el medio más pequeño elementos.
Cuando agrega un nuevo número a la cola, primero verifica cuál es el número de objetos en la cola.
si el número que está agregando es un número par, significa que debe agregarse al máximo-montón ya que ambas colas tienen el mismo tamaño.
Luego verá cuál es el máximo en el montón máximo.
Si es más grande que su número, puede simplemente insertarlo en el montón máximo.
si es más pequeño, lo que significa que su nuevo número podría ser más grande que un número en el montón mínimo.
para que veas cuál es el min en el min-heap.
si su número es menor que el min, de lo que puede insertarlo en el montón máximo, si es más grande, mueva el min en el min-heap al máximo-montón, e inserte su nuevo número en el Min-Heap.
Si el número es un número impar, debe agregar al min-heap ya que max-heap tiene uno más, y así sucesivamente ..
Es un poco complicado, pero si todavía no entiende que no me importa pseudo codificación por usted
Si la cola tiene n elemento, el máximo de max-heap es mayor que al menos n/2 elementos (es decir, elementos en max-heap). Pero, ¿cómo puede estar tan seguro de que el min-heap no tiene ningún elemento menor que max de max-heap, porque si max de max-heap es mayor que cualquier elemento en min-heap, entonces tenemos más de n/2 números que son menos que max de max-heap. Corrígeme si estoy equivocado. – user913359
editaré mi publicación ya que no puedo escribir todo como un comentario – Yarneo
@Yarneo: el artículo trata sobre una * prioridad * cola, mientras que el OP pidió una * cola *. Sé que puedes implementar una cola usando una cola de prioridad dando al i-ésimo elemento como prioridad i (o -i, dependiendo de cómo funcionan tus prioridades), pero eso arruina tu cálculo de la mediana si lo entiendo correctamente: obtendrás el elemento con prioridad media, es decir, el elemento en el medio de la cola ... –
no es la mediana de 2 HRE? –
Lo siento, he cambiado el ejemplo ahora. – user913359
¿tiene la cola una cantidad máxima de objetos que puede contener? ¿Todas las otras funciones de la cola, como push y pop, necesitan permanecer en la misma complejidad? – Yarneo