Un torneo cinético es una estructura de datos cinéticos que funciona como una cola de prioridad para elementos cuyas prioridades cambian como una función continua del tiempo. Se implementa de manera análoga a un "torneo" entre elementos para determinar el "ganador" (elemento máximo o mínimo), con los certificados que imponen el ganador de cada "partido" en el torneo. Admite las operaciones de cola de prioridad habituales: insert , delete y find-max . A menudo se utilizan como componentes de otras estructuras de datos cinéticos, como kinetic nearest pair .
Implementación
Un torneo cinético se organiza en una estructura similar a un árbol binario , donde las hojas contienen los elementos y cada nodo interno contiene el mayor (o menor) de los elementos en sus nodos secundarios . Por lo tanto, la raíz del árbol contiene el elemento máximo (o mínimo) en un momento dado. La validez de la estructura se aplica creando un certificado en cada nodo, que afirma que el elemento en el nodo es el mayor de los dos hijos. Cuando este certificado falla, el elemento en el nodo se cambia (para que sea el elemento en el otro hijo), y se crea un nuevo certificado que representa el nuevo invariante. Si el elemento de este nodo fue un ganador en su nodo padre , entonces el elemento y los certificados en el padre también deben actualizarse recursivamente.
Análisis
Se trata de una estructura de datos O( n ), espacial, responsiva, local, compacta y eficiente.
Capacidad de respuesta : un error de certificado provocará la creación de un nuevo certificado para reemplazar al anterior, que debe colocarse en la cola de eventos . También puede desencadenar cambios en los certificados O(log n ) en sus nodos principales. Cada cambio de certificado requiere una operación de eliminación e inserción en la cola de prioridad de eventos. Cada una de estas requiere un tiempo O(log n ), por lo que la capacidad de respuesta, el tiempo total necesario para procesar un error de certificado, es. Si bien esto se considera responsivo en general, es menos responsivo que otras colas de prioridad cinética, como los montones cinéticos que responden a los errores de certificado con cambios de certificado O(1).
Localidad : cada elemento está involucrado en certificados O(log n ) (por ejemplo, el elemento máximo está involucrado en un certificado en cada uno de sus padres hasta el nodo raíz). Nuevamente, si bien esto se considera local, un montón cinético es mucho más local.
Compacidad : esta es una estructura muy compacta, que contiene O( n ) certificados (exactamente uno para cada borde del árbol).
Eficiencia : Los montones cinéticos son muy eficientes, con el número de eventos internos (cambios de certificado) siendo solo un factor de O(log n ) más que el número de eventos externos . Específicamente, para una colección de trayectorias espacio-temporales donde cada par se interseca como máximo s veces, el torneo cinético procesa O(λ s+2 log n ) eventos en O(λ s+2 log 2 n ) tiempo, donde λ s+2 es una secuencia de Davenport-Schinzel . Además, las inserciones y eliminaciones causan O(log n ) cambios de certificado cada una. Cada cambio de certificado toma O(log n ) tiempo, que está determinado por el tiempo requerido para ejecutar la actualización de la cola de eventos.
Referencias
Basch, J. 1999. Estructuras de datos cinéticos. Tesis doctoral, Departamento de Ciencias de la Computación, Universidad de Stanford. [1]
