java - pilas - tda lista
Estructura de datos en cola que respalda el rápido hallazgo de k-ésimo elemento más grande (3)
Me enfrento a un problema que requiere una estructura de datos Queue que soporte el rápido hallazgo de k-ésimo elemento más grande.
Los requisitos de esta estructura de datos son los siguientes:
Los elementos en la cola no son necesariamente enteros, pero deben ser comparables entre sí, es decir, podemos decir cuál es mayor cuando comparamos dos elementos (también pueden ser iguales).
La estructura de datos debe soportar enqueue (agrega el elemento en la cola) y dequeue (elimina el elemento en la cabecera).
Puede encontrar rápidamente el k-ésimo elemento más grande en la cola, la nota p k no es una constante.
Puede suponer que las operaciones en cola, dequeue y k-ésimo elemento más grande encuentran que todas ocurren con la misma frecuencia.
Mi idea es usar un árbol de búsqueda binaria equilibrado modificado. El árbol es el mismo que el árbol ordinario de búsqueda binaria equilibrada, excepto que cada nodo i se aumenta con otro campo n i , n i denota el número de nodos contenidos en el subárbol con el nodo raíz i . Las operaciones antes mencionadas son compatibles de la siguiente manera:
Para simplificar, supongamos que todos los elementos son distintos.
Enqueue (x) : x se inserta primero en el árbol, supongamos que el nodo correspondiente es el nodo t , agregamos el par (x, puntero al nodo t ) a la cola.
Dequeue : supongamos que (e1, nodo 1 ) es el elemento en la cabecera, el nodo 1 es el puntero en el árbol correspondiente a e1. Eliminamos el nodo 1 del árbol y eliminamos (e1, nodo 1 ) de la cola.
K-ésimo hallazgo del elemento más grande : supongamos que el nodo raíz es nodo raíz , sus dos hijos son nodo izquierdo y nodo derecho (supongamos que todos existen), comparamos K con n raíz , pueden ocurrir tres casos:
si K <n izquierda , encontramos el K-ésimo elemento más grande en el subárbol izquierdo de n root ;
si K> n root -n right encontramos el (mayor raíz Kn + n) el elemento más grande en el subárbol derecho de n root ;
de lo contrario n root es el nodo que queremos.
La complejidad de tiempo de las tres operaciones es O (log N ), donde N es el número de elementos actualmente en la cola.
¿Cómo puedo acelerar las operaciones mencionadas anteriormente? ¿Con qué estructuras de datos y cómo?
Encontré un artículo interesante:
Preguntas de Top-k sobre flujos inciertos publicados en VLDB 2008 y citados por 71.
https://www.cse.ust.hk/~yike/wtopk.pdf
VLDB es la mejor conferencia en el área de investigación de bases de datos, y el número de citas demuestra que la estructura de datos realmente funciona.
El documento parece bastante difícil, pero si realmente necesita mejorar su estructura de datos, le sugiero que lea este documento o documentos en la página de referencia de este documento.
Nota: no se puede lograr mejor que O(logn) para todos, en el mejor de los casos, debe "elegir" cuál es el que más le importa. (De lo contrario, podría ordenar O(n) alimentando la matriz al DS y consultando los elementos 1, 2, 3, ... enésimo)
- Usar una lista de omisiones en lugar de una BST equilibrada, ya que la estructura ordenada puede reducir la complejidad de dequeue a
O(1)promedio de casos . No afecta la complejidad de ninguna otra operación.
Para eliminar de una lista de omisiones, todo lo que necesita hacer es llegar al elemento usando el puntero del encabezado de la cola, seguir los enlaces hacia arriba y eliminar cada uno. El número esperado de nodos necesarios para eliminarse es 1 + 1/2 + 1/4 + ... = 2. - encontrar Kth se puede lograr en
O(logK)comenzando desde el nodo más leftest (y no desde la raíz) y ascendiendo hasta que encuentre que tiene "más hijos que necesitaba", y luego trate el nodo recién encontrado como la raíz acabada como el algoritmo en la pregunta. Aunque es mejor en la complejidad asintótica, el factor constante es el doble.
También puedes usar un árbol de dedo .
Por ejemplo, una cola de prioridad puede implementarse etiquetando los nodos internos por la prioridad mínima de sus elementos secundarios en el árbol, o una lista / matriz indexada puede implementarse con un etiquetado de nodos por el recuento de las hojas en sus elementos secundarios. Los árboles de los dedos pueden proporcionar O (1) contras amortiguados, reversibles, cdr, Anexar y dividir; y puede adaptarse para ser secuencias indexadas u ordenadas.
También tenga en cuenta que al ser una estructura puramente funcional hace que esta sea una buena opción para el uso simultáneo.