Estructuras de datos pregunta

Question

Esta pregunta es de un examen que tuve, y no pude resolverlo y quería ver cuál es la respuesta (esto no es tarea, ya que no me ayudará en nada más que conocimiento).

Necesitamos crear una estructura de datos para contener elementos cuyas claves son números reales.
La estructura de datos debe tener estas funciones:
Build (s, array): construye la estructura de datos S con n elementos en O (n)
Insert (S, K) y eliminar (S, x) en O (lgn) (k es un elemento, x es un puntero a él en la estructura de datos)
Delete-Minimal-Positive (S): elimina el elemento con la clave positiva mínima
Modo (S): devuelve la clave más frecuente en S en O (1)

Ahora, construir en O (n) generalmente significa que debe usarse un montón, pero eso no permite encontrar frecuencias. No pude encontrar ninguna manera de hacer esto. Lo mejor que se me ocurre es construir un Árbol Rojo-Negro (O (nlgn)) que se utilizará para construir un montón de frecuencia.

Me muero por saber la respuesta ...

Gracias!

Answer 1

Bueno, puede usar una tabla hash para calcular el número de ocurrencias de números reales distintos en O (1) tiempo amortizado, y luego usar un montón estándar donde los artículos son pares (número real, número de apariciones) y el montón está ordenado según el campo de cantidad de apariciones.

Cuando inserta una clave o elimina una, aumenta o disminuye el número de campos de ocurrencias por uno, o en los casos extremos agrega o elimina un elemento de montón. En ambos casos, debe filtrar hacia arriba/abajo porque el campo de ordenamiento ha cambiado.

Suponiendo que la tabla hash tiene una operación O (1), tiene una tabla hash estándar de pila + O (1) y obtiene todas las operaciones anteriores dentro de los límites de tiempo. En particular, obtienes el "modo" leyendo el elemento raíz del montón.

Answer 2

Creo que la siguiente solución será aceptable. Se basa en dos Construcciones de datos:

1. árbol rojo-negro
2. montón binario

montón binario sostiene tupla, que contienen (valor de elemento, frequence de elemento), montón está construida en frecuencias, entonces nos da la habilidad de encontrar el modo en O (1).

árbol negro rojo contiene una tupla que sostienen (valor del elemento, puntero al mismo valor del elemento en el montón)

Cuando es necesario insertar nuevo elemento, que tratará de encontrar el elemento (que toma O (log n)), si la búsqueda fue exitosa, que ir al puntero del elemento fundado en árbol RB, aumentar la frecuencia y reconstruir el montón (también O (log n)). Si la búsqueda no encontró ese elemento, no lo inserte en el árbol RB (O (log n)) y para acumularlo con value = (element, 1) (también O (1)), establezca un puntero en RB-tree en new elemento en el montón.

edificio inicial se llevará a O (n), debido a la construcción de ambas estructuras de conjunto de n elemento de toma O (n).

Lo sentimos, si no me pierda algo.

Answer 3

Utilizando solo el modelo de comparación , no hay ninguna solución a este problema.

El Element Distinctness Problem tiene demostrable Omega (nlogn) límites inferiores. Este problema (distinción de elementos) es básicamente el problema de determinar si todos los elementos de una matriz son distintos.

Si hubo una solución a su problema, entonces podríamos responder el problema de distinción de elementos en O (n) tiempo (encontrar el elemento más frecuente en O (n) tiempo, y ver si hay más de una instancia de ese elemento, nuevamente en O (n) tiempo).

Por lo tanto, le sugiero que pregunte a su profesor para el modelo computacional.

Answer 4

Para frecuencias:
Cada entrada está ligada a bi-directionaly propia frecuencias/contadores (tabla hash uso)
Las frecuencias están en lista enlazada.
existe la necesidad de mover la frecuencia hacia arriba/abajo sobre lista enlazada, (eliminando elemento de inserción), pero la diferencia máxima de 1.

frecuencias son que se vincula con el puntero del elemento 1 y -1 frecuencia.

(hay excepciones, pero pueden ser manejados)