Reinventarlo

¿Cuál elegir?

Un sistema cambia prioridades muy a menudo: cada elemento cambia de prioridad decenas de veces antes de salir.

Una cola tiene 100 000 elementos y cada uno cambia de prioridad unas 30 veces antes de salir. ¿Qué solución conviene más?Buscar el elemento recorriendo el heap y reconstruirlo: O(n), pero muy simpleUn array ordenado por prioridad: cambiar una prioridad es mover un elementoEl índice de posiciones: cada cambio cuesta O(log n) y el heap no creceEl borrado perezoso: cada cambio es una inserción de O(log n) sin índice que mantener