En informática , los algoritmos de fusión de k vías o fusiones multivía son un tipo específico de algoritmos de fusión de secuencias que se especializan en tomar k listas ordenadas y fusionarlas en una única lista ordenada. Estos algoritmos de fusión generalmente se refieren a algoritmos de fusión que toman una cantidad de listas ordenadas mayor que dos. Las fusiones bidireccionales también se conocen como fusiones binarias. La fusión de k vías también es un algoritmo de ordenamiento externo.
La fusión de dos vías, o fusión binaria, se ha estudiado ampliamente debido a su papel clave en la ordenación por fusión . Un ejemplo de ello es la fusión clásica que aparece con frecuencia en los ejemplos de ordenación por fusión. La fusión clásica genera el elemento de datos con la clave más baja en cada paso; dadas algunas listas ordenadas, produce una lista ordenada que contiene todos los elementos en cualquiera de las listas de entrada, y lo hace en un tiempo proporcional a la suma de las longitudes de las listas de entrada.
Denotemos por A[1..p] y B[1..q] dos matrices ordenadas en orden creciente. Además, denotemos por C[1..n] la matriz de salida. El algoritmo de fusión de 2 vías canónico [1] almacena los índices i, j y k en A, B y C respectivamente. Inicialmente, estos índices se refieren al primer elemento, es decir, son 1. Si A[i] < B[j], entonces el algoritmo copia A[i] en C[k] y aumenta i y k. De lo contrario, el algoritmo copia B[j] en C[k] y aumenta j y k. Surge un caso especial si i o j han llegado al final de A o B. En este caso, el algoritmo copia los elementos restantes de B o A en C y termina.
El problema de fusión de k vías consiste en fusionar k matrices ordenadas para producir una única matriz ordenada con los mismos elementos. Denote por n el número total de elementos. n es igual al tamaño de la matriz de salida y la suma de los tamaños de las k matrices de entrada. Para simplificar, suponemos que ninguna de las matrices de entrada está vacía. Como consecuencia , lo que simplifica los tiempos de ejecución informados. El problema se puede resolver en tiempo de ejecución con espacio. Existen varios algoritmos que logran este tiempo de ejecución.
El problema se puede resolver fusionando iterativamente dos de las k matrices mediante una fusión de dos vías hasta que solo quede una matriz. Si las matrices se fusionan en un orden arbitrario, el tiempo de ejecución resultante es solo O(kn). Esto no es óptimo.
El tiempo de ejecución se puede mejorar fusionando iterativamente el primero con el segundo, el tercero con el cuarto, y así sucesivamente. Como el número de matrices se reduce a la mitad en cada iteración, solo hay Θ(log k) iteraciones. En cada iteración, cada elemento se mueve exactamente una vez. Por lo tanto, el tiempo de ejecución por iteración está en Θ(n), ya que n es el número de elementos. Por lo tanto, el tiempo de ejecución total está en Θ(n log k).
Podemos mejorar aún más este algoritmo fusionando iterativamente las dos matrices más cortas. Está claro que esto minimiza el tiempo de ejecución y, por lo tanto, no puede ser peor que la estrategia descrita en el párrafo anterior. Por lo tanto, el tiempo de ejecución está en O(n log k). Afortunadamente, en casos límite el tiempo de ejecución puede ser mejor. Consideremos, por ejemplo, el caso degenerado, donde todas las matrices menos una contienen solo un elemento. La estrategia explicada en el párrafo anterior necesita un tiempo de ejecución de Θ(n log k), mientras que la mejorada solo necesita un tiempo de ejecución de Θ(n + k log k).
En este caso, fusionaríamos simultáneamente las k-carreras.
Una implementación sencilla escanearía todas las matrices k para determinar el mínimo. Esta implementación sencilla da como resultado un tiempo de ejecución de Θ(kn). Tenga en cuenta que esto se menciona solo como una posibilidad, a los efectos de la discusión. Si bien funcionaría, no es eficiente.
Podemos mejorar esto calculando el elemento más pequeño más rápido. Al usar heaps , árboles de torneo o árboles de distribución , el elemento más pequeño se puede determinar en tiempo O(log k). Por lo tanto, los tiempos de ejecución resultantes están en O(n log k).
El heap es el método más utilizado, aunque en la práctica un árbol de torneos es más rápido. Un heap utiliza aproximadamente 2*log(k) comparaciones en cada paso porque maneja el árbol desde la raíz hasta el final y necesita comparar ambos hijos de cada nodo. Mientras tanto, un árbol de torneos solo necesita comparaciones log(k) porque comienza en la parte inferior del árbol y avanza hasta la raíz, haciendo solo una comparación en cada capa. Por lo tanto, el árbol de torneos debería ser la implementación preferida.
La idea es mantener un min-heap de las k listas, cada una identificada por su elemento actual más pequeño. Un algoritmo simple crea un buffer de salida con nodos del heap. Comience por crear un min-heap de nodos, donde cada nodo consta de un elemento de cabeza de la lista y el resto (o cola) de la lista. Debido a que las listas se ordenan inicialmente, la cabeza es el elemento más pequeño de cada lista; la propiedad heap garantiza que la raíz contenga el elemento mínimo de todas las listas. Extraiga el nodo raíz del heap, agregue el elemento de cabeza al buffer de salida, cree un nuevo nodo a partir de la cola e insértelo en el heap. Repita hasta que solo quede un nodo en el heap, en cuyo punto simplemente agregue esa lista restante (cabeza y cola) al buffer de salida.
Utilizando punteros, un algoritmo de montón in situ [2] asigna un montón mínimo de punteros en las matrices de entrada. Inicialmente, estos punteros apuntan a los elementos más pequeños de la matriz de entrada. Los punteros se ordenan por el valor al que apuntan. En un paso de preprocesamiento O(k), el montón se crea utilizando el procedimiento estándar heapify. Después, el algoritmo transfiere iterativamente el elemento al que apunta el puntero raíz, incrementa este puntero y ejecuta el procedimiento estándar de disminución de clave sobre el elemento raíz. El tiempo de ejecución del procedimiento de aumento de clave está limitado por O(log k). Como hay n elementos, el tiempo de ejecución total es O(n log k).
Tenga en cuenta que la operación de reemplazar la clave y realizar iterativamente la disminución de la clave o la reducción gradual no son compatibles con muchas bibliotecas de colas de prioridad, como C++ stl y Java. Realizar una función de extracción, min e inserción es menos eficiente.
El árbol de torneos [3] se basa en un torneo de eliminación, como en las competiciones deportivas. En cada juego compiten dos de los elementos de entrada. El ganador pasa a la siguiente ronda. Por lo tanto, obtenemos un árbol binario de juegos. La lista está ordenada en orden ascendente, por lo que el ganador de un juego es el menor de ambos elementos.
Para la fusión de k-way, es más eficiente almacenar solo al perdedor de cada juego (ver imagen). Por lo tanto, la estructura de datos se llama árbol de perdedores. Al construir el árbol o reemplazar un elemento con el siguiente de su lista, aún promovemos al ganador del juego a la parte superior. El árbol se llena como en un partido deportivo, pero los nodos solo almacenan al perdedor. Por lo general, se agrega un nodo adicional sobre la raíz que representa al ganador general. Cada hoja almacena un puntero a una de las matrices de entrada. Cada nodo interno almacena un valor y un índice. El índice de un nodo interno indica de qué matriz de entrada proviene el valor. El valor contiene una copia del primer elemento de la matriz de entrada correspondiente.
El algoritmo añade iterativamente el elemento mínimo al resultado y luego elimina el elemento de la lista de entrada correspondiente. Actualiza los nodos en la ruta desde la hoja actualizada hasta la raíz ( selección de reemplazo ). El elemento eliminado es el ganador general. Por lo tanto, ha ganado cada juego en la ruta desde la matriz de entrada hasta la raíz. Al seleccionar un nuevo elemento de la matriz de entrada, el elemento debe competir contra los perdedores anteriores en la ruta a la raíz. Cuando se utiliza un árbol de perdedores, el compañero para repetir los juegos ya está almacenado en los nodos. El perdedor de cada juego repetido se escribe en el nodo y el ganador se promueve iterativamente a la parte superior. Cuando se llega a la raíz, se encontró el nuevo ganador general y se puede utilizar en la siguiente ronda de fusión.
Las imágenes del árbol del torneo y del árbol de perdedores en esta sección utilizan los mismos datos y se pueden comparar para comprender el modo en que funciona un árbol de perdedores.
Un árbol de torneo se puede representar como un árbol binario balanceado agregando centinelas a las listas de entrada (es decir, agregando un miembro al final de cada lista con un valor de infinito) y agregando listas nulas (que comprenden solo un centinela) hasta que el número de listas sea una potencia de dos. El árbol balanceado se puede almacenar en una sola matriz. Se puede llegar al elemento padre dividiendo el índice actual por dos.
Cuando se actualiza una de las hojas, se repiten todos los juegos desde la hoja hasta la raíz. En el siguiente pseudocódigo , se utiliza un árbol orientado a objetos en lugar de una matriz porque es más fácil de entender. Además, se supone que la cantidad de listas a fusionar es una potencia de dos.
función fusionar(L1, ..., Ln) buildTree(cabezas de L1, ..., Ln) mientras el árbol tiene elementos ganador := arbol.ganador Salida ganadora.valor nuevo := ganador.índice.siguiente replayGames(ganador, nuevo) // Selección de reemplazo
función replayGames(nodo, nuevo) perdedor, ganador := playGame(nodo, nuevo) nodo.valor := perdedor.valor nodo.índice := perdedor.índice si nodo != raíz replayGames(nodo.padre, ganador)
función buildTree(elementos) siguienteCapa := nueva Matriz() mientras los elementos no estén vacíos el1 := elementos.take() el2 := elementos.take() perdedor, ganador := playGame(el1, el2) padre := nuevo Nodo(el1, el2, perdedor) siguienteCapa.add(padre) si nextLayer.size == 1 devuelve nextLayer // solo root de lo contrario devuelve buildTree(nextLayer)
Al principio, el árbol se crea en un tiempo Θ(k). En cada paso de la fusión, solo es necesario repetir los juegos en la ruta desde el nuevo elemento hasta la raíz. En cada capa, solo se necesita una comparación. Como el árbol está equilibrado, la ruta desde una de las matrices de entrada hasta la raíz contiene solo Θ(log k) elementos. En total, hay n elementos que deben transferirse. Por lo tanto, el tiempo de ejecución total resultante es Θ(n log k). [3]
La siguiente sección contiene un ejemplo detallado del paso de selección de reemplazo y un ejemplo de una fusión completa que contiene múltiples selecciones de reemplazo.
Los juegos se repiten de abajo hacia arriba. En cada capa del árbol, compiten el elemento almacenado actualmente en el nodo y el elemento que se proporcionó desde la capa inferior. El ganador asciende a la cima hasta que encontramos al nuevo ganador general. El perdedor se almacena en el nodo del árbol.
Para ejecutar la fusión, el elemento más pequeño se reemplaza repetidamente con el siguiente elemento de entrada. Después de eso, se repiten los juegos hasta el principio.
Este ejemplo utiliza cuatro matrices ordenadas como entrada.
{2, 7, 16}{5, 10, 20}{3, 6, 21}{4, 8, 9}El algoritmo se inicia con los encabezados de cada lista de entrada. Con estos elementos, se construye un árbol binario de perdedores. Para la fusión, el elemento de lista más bajo, 2, se determina observando el elemento mínimo general en la parte superior del árbol. Luego, se extrae ese valor y su hoja se rellena con 7, el siguiente valor en la lista de entrada. Los juegos en el camino hacia la cima se repiten como en la sección anterior sobre la selección de reemplazo. El siguiente elemento que se elimina es 3. A partir del siguiente valor en la lista, 6, los juegos se repiten hasta la raíz. Esto se repite hasta que el mínimo del árbol es igual a infinito.
Se puede demostrar que no existe ningún algoritmo de fusión de k vías basado en comparación con un tiempo de ejecución en O ( n f(k)) donde f crece asintóticamente más lento que un logaritmo y n es el número total de elementos. (Excluyendo datos con distribuciones deseables, como rangos disjuntos). La prueba es una reducción directa de la ordenación basada en comparación. Supongamos que existiera un algoritmo de este tipo, entonces podríamos construir un algoritmo de ordenación basado en comparación con un tiempo de ejecución O ( n f( n )) de la siguiente manera: Cortar la matriz de entrada en n matrices de tamaño 1. Fusionar estas n matrices con el algoritmo de fusión de k vías. La matriz resultante se ordena y el algoritmo tiene un tiempo de ejecución en O ( n f( n )). Esto es una contradicción con el resultado bien conocido de que no existe ningún algoritmo de ordenación basado en comparación con un tiempo de ejecución en el peor de los casos inferior a O ( n log n ).
Las fusiones de k -vías se utilizan en procedimientos de ordenamiento externo. [4] Los algoritmos de ordenamiento externo son una clase de algoritmos de ordenamiento que pueden manejar cantidades masivas de datos. La ordenación externa es necesaria cuando los datos que se están ordenando no caben en la memoria principal de un dispositivo informático (normalmente RAM) y, en su lugar, deben residir en la memoria externa más lenta (normalmente un disco duro). Los algoritmos de fusión de k -vías suelen tener lugar en la segunda etapa de los algoritmos de ordenamiento externo, de forma muy similar a como lo hacen para la ordenación por fusión.
Una fusión multidireccional permite fusionar los archivos fuera de la memoria en menos pasos que en una fusión binaria. Si hay 6 ejecuciones que deben fusionarse, entonces una fusión binaria necesitaría 3 pasos de fusión, a diferencia del paso único de una fusión de 6 vías. Esta reducción de los pasos de fusión es especialmente importante considerando la gran cantidad de información que generalmente se clasifica en primer lugar, lo que permite mayores aceleraciones y también reduce la cantidad de accesos a almacenamiento más lento.