Un colgador cinético es una versión aleatoria de un montón cinético cuyo rendimiento es fácil de analizar con precisión. Un colgador cinético satisface la propiedad del montón (la prioridad de cada elemento es más alta que la prioridad de sus elementos secundarios) pero relaja el requisito de que la estructura del árbol debe estar estrictamente equilibrada, por lo que las inserciones y eliminaciones se pueden aleatorizar. Como resultado, la estructura del colgador cinético tiene la propiedad de que se extrae uniformemente al azar del espacio de todas las posibles estructuras en forma de montón en sus elementos.
La estructura del colgador cinético (incluidos los certificados y la cola de eventos) es exactamente igual que la estructura del montón cinético, pero sin el requisito de equilibrio. Por lo tanto, consta de una cola de prioridad eficiente (la cola de eventos) para mantener los tiempos de falla del certificado, así como una estructura de árbol principal (no necesariamente equilibrada) en forma de montón en la que se almacenan los elementos. Hay un certificado asociado con cada borde que aplica la propiedad del montón (prioridad del padre > prioridad del niño) a lo largo de ese borde.
La operación característica en un colgador cinético es " colgar ", que se define de la siguiente manera (se hace una distinción entre un nodo en la estructura de árbol y el elemento almacenado en él).Cuelgue (Nodo n, Elemento e)
La principal diferencia entre el colgador cinético y el montón cinético está en las operaciones clave, que se implementan de la siguiente manera en un colgador cinético:
Todas estas operaciones dan como resultado una estructura uniformemente aleatoria para la percha, con una altura esperada de O(log n).
da Fonseca, Guilherme D. and de Figueiredo, Celina MH and Carvalho, Paulo CP "Percha cinética" (PDF) . Cartas de procesamiento de información. págs. 151–157. Archivado desde el original (PDF) el 24 de mayo de 2015 . Consultado el 17 de mayo de 2012 .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )