Un calentador cinético es una cola de prioridad cinética similar a un montón cinético , que utiliza la aleatorización para simplificar su análisis de forma similar a un treap . Específicamente, cada elemento tiene una clave aleatoria asociada a él además de su prioridad (que cambia como una función continua del tiempo como en todas las estructuras de datos cinéticos ). El calentador cinético es simultáneamente un árbol de búsqueda binario en las claves de elementos y un montónen las prioridades de los elementos. El calentador cinético logra límites de rendimiento asintótico (esperados) iguales a las mejores colas de prioridad cinética. En la práctica, sin embargo, es menos eficiente ya que las claves aleatorias adicionales deben almacenarse y el procedimiento para manejar la falla del certificado es una rotación (relativamente complicada) en lugar de un simple intercambio. [1]
Si cada elemento tiene una clave y una prioridad asociada, entonces hay una estructura de árbol única que es simultáneamente un árbol de búsqueda en las claves y un montón en las prioridades: esta estructura corresponde al treap (si las prioridades se eligen al azar) o el calentador cinético (si las claves se eligen al azar).
La validez de la estructura de árbol se garantiza mediante la creación de un certificado en cada borde que aplica la propiedad del montón en ese borde. La principal diferencia operativa entre un montón cinético y un calentador cinético está en cómo responden a las fallas de certificado. Cuando falla un certificado en un borde, un calentador cinético realizará una rotación alrededor de los nodos que fallaron (en lugar del intercambio que realizaría un montón cinético).
Por ejemplo, considere los elementos B (con padre F ) y su hijo izquierdo D (con hijo derecho C ). Cuando falla el certificado [ B > D ] en el borde BD , el árbol rotará alrededor de este borde. Por lo tanto, en este caso, la estructura resultante tiene D en lugar de B , C se convierte en un elemento secundario de B en lugar de D , y hay tres cambios de certificado [B>D] reemplazados por [D>B], [D>C] reemplazados por [B>C] y [F>B] reemplazados por [F>D]. Todo lo demás se queda igual.