torneo cinético
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 haciendo valer el ganador de cada "partido" en el torneo. Admite las operaciones de cola de prioridad habituales: insertar , eliminar y encontrar-máx . A menudo se utilizan como componentes de otras estructuras de datos cinéticos, como el par cinético más cercano .
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 . Así, la raíz del árbol contiene el elemento máximo (o mínimo) en un momento dado. La validez de la estructura se impone mediante la creación de un certificado en cada nodo, que afirma que el elemento del nodo es el mayor de los dos hijos. Cuando este certificado falla, el elemento en el nodo se cambia (para ser el elemento en el otro elemento secundario) y se crea un nuevo certificado que representa el nuevo invariante. Si el elemento este nodo fue un ganador en su nodo padre, entonces el elemento y los certificados en el padre también deben actualizarse recursivamente.
