Cola de prioridad cinética

---

Una cola de prioridad cinética es una estructura de datos cinéticos abstractos . Es una variante de una cola de prioridad diseñada para mantener el elemento de prioridad máxima (o mínima) (par clave-valor) cuando la prioridad de cada elemento cambia como una función continua del tiempo. Las colas de prioridad cinética se han utilizado como componentes de varias estructuras de datos cinéticos, así como para resolver algunos problemas no cinéticos importantes, como el problema del conjunto k y el problema de intersección de segmentos rojos y azules conectados.

Hay varias variantes de colas de prioridad cinética, que admiten las mismas operaciones básicas pero tienen diferentes garantías de rendimiento. Algunas de las implementaciones más comunes son los montones cinéticos , que son fáciles de implementar pero no tienen límites de rendimiento teóricos estrictos, y sus variantes aleatorias, calentadores cinéticos y colgadores cinéticos , que son más fáciles de analizar. También hay una estructura similar a un montón basada en la estructura de datos de casco convexo dinámico ^[1] que logra un mejor rendimiento para el movimiento afín de las prioridades, pero no admite trayectorias curvas. El torneo cinéticoes otra implementación comúnmente utilizada. Logra, de manera determinista, los mismos límites de rendimiento que el calentador o el colgador, sin embargo, es menos local y receptivo que las estructuras de datos basadas en montones.

Aquí, denota la función inversa de Ackermann . -Las curvas que se cruzan se refieren a las curvas en las que cada par tiene la mayoría de las intersecciones, y se refieren a un término en la secuencia de Davenport-Schinzel , que da el tamaño máximo de la envolvente superior de las curvas que se cruzan. es la mayor cantidad de elementos en la cola en un momento dado, mientras que se refiere a la cantidad total de elementos que alguna vez están en la cola.${\displaystyle \alpha (x)}$${\displaystyle \delta }$${\displaystyle \delta }$${\displaystyle \lambda _{\delta }(n)}$${\displaystyle n}$ ${\displaystyle \delta -}$${\displaystyle n}$${\displaystyle m}$

Las colas de prioridad cinética se utilizan como parte de otras estructuras/algoritmos de datos cinéticos, como el par más cercano cinético , el corte máximo cinético ^[3] o el agrupamiento cinético . ^[4]

También se pueden usar para resolver problemas como la programación de transmisiones ^[5] o el problema de intersección de segmentos rojos y azules conectados. ^[6]

---