Este artículo explora una estructura algebraica llamada 'monus' y su aplicación en algoritmos de búsqueda y ordenamiento, particularmente en el contexto de montículos (heaps). Un montículo es una estructura de datos en forma de árbol donde el valor de cada nodo es menor o igual que el de sus hijos, lo que permite una recuperación eficiente del elemento mínimo (popMin). Tradicionalmente, los montículos almacenan el valor completo de cada nodo. Sin embargo, el monus permite una representación más eficiente al almacenar solo las diferencias de peso entre un nodo y sus padres.
Un monus es esencialmente un monoide (una estructura algebraica con una operación de combinación asociativa y un elemento identidad) que también tiene una operación de 'subtracción parcial' (denotada por ∸) y un orden definido en términos de la operación de combinación. Esta estructura es útil cuando los pesos involucrados forman un monoide, como en algoritmos de búsqueda de caminos más cortos en grafos, donde la combinación de costos de caminos se realiza de manera monoidal. El orden en el monus permite definir la relación de menor o igual que entre los pesos.
La implementación de montículos utilizando monuses ofrece ventajas significativas. En lugar de almacenar el peso completo en cada nodo, se almacena la diferencia entre el peso del nodo y el de su padre. Esto simplifica operaciones como la adición de una cantidad a todos los pesos del montículo, que se puede realizar simplemente agregando la cantidad al peso de la raíz. El artículo presenta una implementación en Haskell, incluyendo una clase para monuses y una implementación de montículos de emparejamiento (pairing heaps), conocidos por su eficiencia. La clave de esta implementación reside en el uso de la operación ∸ al combinar montículos, asegurando que cada nodo hijo almacene solo la diferencia de peso con respecto a su padre. Finalmente, se muestra cómo usar esta estructura para implementar un algoritmo de ordenamiento (sortOn) eficiente.
En resumen, el uso de monuses en montículos proporciona una forma elegante y eficiente de representar y manipular pesos, lo que lleva a optimizaciones en algoritmos de búsqueda, ordenamiento y otras aplicaciones que involucran montículos.