Un montón cinético es una estructura de datos cinéticos , obtenida por la cinetización de un montón . Está diseñado para almacenar elementos (claves asociadas a prioridades) donde la prioridad va cambiando en función continua del tiempo. Como un tipo de cola de prioridad cinética , mantiene el elemento de máxima prioridad almacenado en ella. La estructura de datos del montón cinético funciona almacenando los elementos como un árbol que satisface la siguiente propiedad del montón: si B es un nodo secundario de A , entonces la prioridad del elemento en A debe ser mayor que la prioridad del elemento en B. Esta propiedad del montón se aplica usandocertificados a lo largo de cada borde, por lo que, al igual que otras estructuras de datos cinéticos, un montón cinético también contiene una cola de prioridad (la cola de eventos) para mantener los tiempos de falla del certificado.
Un montón regular puede ser kinetized aumentando con un certificado [ A > B ] para cada par de nodos A , B tal que B es un nodo hijo de A . Si el valor almacenado en un nodo X es una función f X ( t ) del tiempo, entonces este certificado solo es válido mientras f A ( t ) > f B ( t ) . Por lo tanto, la falla de este certificado debe programarse en la cola de eventos en un tiempo t tal que f A ( t ) > fB ( t ).
Todas las fallas de certificados se programan en la "cola de eventos", que se supone que es una cola de prioridad eficiente cuyas operaciones toman tiempo O (log n ) .
Cuando un certificado [ A > B ] falla, la estructura de datos debe intercambiar A y B en el montón y actualizar los certificados en los que estaba presente cada uno de ellos.
Por ejemplo, si B (con los nodos secundarios Y y Z ) era un nodo secundario de A (con los nodos secundarios B y C y el nodo principal X ) y el certificado [ A > B ] falla, entonces la estructura de datos debe intercambiar B y A , luego reemplace los certificados antiguos (y los eventos programados correspondientes) [ A > B ], [ A < X ], [ A > C ], [ B > Y ], [ B >Z ] con nuevos certificados [ B > A ], [ B < X ], [ B > C ], [ A > Y ] y [ A > Z ].
Por lo tanto, suponiendo que los eventos no degeneran (no ocurren dos eventos al mismo tiempo), solo es necesario cancelar y reprogramar un número constante de eventos, incluso en el peor de los casos.