Un equipo de investigadores del Instituto Max Planck de Informática, la ETH Zúrich y la Universidad Técnica de Dresde ha presentado el sync heap, una estructura de datos tipo montículo (cola de prioridad) que desacopla la operación de borrar el mínimo de la revelación de su identidad al usuario. El trabajo, disponible como preprint en arXiv, cuestiona un supuesto clásico de los libros de texto: que, en el modelo de comparación, al menos una de las dos operaciones básicas —insertar un elemento o eliminar el mínimo— debe costar tiempo logarítmico.
Los autores demuestran que la barrera del orden n log n propia del ordenamiento no es intrínseca al borrado, sino al coste informativo de mostrar inmediatamente qué elemento se eliminó. Si el usuario consulta el estado de la estructura solo un número constante de veces, tanto las inserciones como los borrados pueden realizarse en tiempo constante amortizado. La estructura ejecuta n operaciones con d borrados silenciosos y k observaciones en tiempo total O(n + d log k).
Como aplicación práctica, el sync heap mejora de O(n log n) a O(n), óptimo, la resolución de un problema clásico de planificación de tareas a tiempo unitario. El diseño se apoya en el soft heap introducido por Chazelle, un montículo relajado que permite acelerar las operaciones a cambio de una corrupción controlada de un número limitado de claves.
El sync heap es determinista, se basa solo en comparaciones y logra resultados asintóticamente óptimos, lo que lo convierte en una contribución teórica relevante en el área de algoritmos y estructuras de datos.