Cómo fusionar tres matrices ordenadas en una sola matriz ordenada de manera eficiente

Puede usar el montón para fusionar cualquier número de matrices ordenadas.

Digamos que hay matrices [math] k [/ math] ([math] A_1, A_2, A_3, …., A_k [/ math]) y cada matriz tiene un tamaño [math] n_1, n_2, n_3, … .. n_k [/ math] respectivamente.

El algoritmo es el siguiente.

1. Cree una matriz [matemática] A [/ matemática] de tamaño [matemática] n_1 + n_2 + n_3 +…. + n_k [/ math] es decir, suma de tamaños de todas las matrices. Por ejemplo, supongamos que tenemos 3 matrices [matemáticas] A_1, A_2, A_3 [/ matemáticas] con tamaños [matemáticas] 5, 8, 3 [/ matemáticas] respectivamente. Crear matriz [math] A [/ math] con tamaño [math] 5 + 8 + 3 [/ math] es decir, [math] 16 [/ math] ( int[] A = new int[16] )
2. Cree un montón mínimo con el primer elemento de cada una de las matrices ordenadas. Por ejemplo, cree un montón mínimo con elementos [matemática] A_1 [0], A_2 [0], A_3 [0],… .., A_k [0] [/ matemática]. En un montón mínimo, el elemento mínimo siempre es el elemento raíz del montón.
3. Repita los siguientes pasos tantas veces como el tamaño de la matriz final [matemática] A, [/ matemática] es decir, [matemática] n_1 + n_2 + n_3 +…. + n_k [/ matemáticas]

1. Ejecute la operación getMini() en el montón que devuelve el elemento mínimo del montón y agregue este elemento a la matriz de resultados, es decir, [math] A [/ math]. Como ya se dijo, el elemento mínimo siempre es la raíz del montón.
2. Ahora reemplace el elemento raíz con el siguiente elemento en la matriz a la que pertenece la raíz. Por ejemplo, en el montón realizado (en el paso 2 ) con elementos [matemática] A_1 [0], A_2 [0], A_3 [0],… .., A_k [0] [/ matemática], digamos ese elemento raíz es [matemática] A_6 [0] [/ matemática], reemplace la raíz con [matemática] A_6 [1] [/ matemática]. Si la matriz llega al final del ciclo, reemplácela con [math] \ infty [/ math]. Por ejemplo, si la raíz es [matemática] A_6 [n_6 – 1] [/ matemática], es decir, el último elemento en la matriz [matemática] A_6 [/ matemática], después de ejecutar el paso a, reemplace la raíz con [matemática] \ infty [/ matemáticas].
3. Ejecute la operación minHeapify() que reestructura el montón para retener la propiedad del montón mínimo.

Mira esto y esto para más detalles.

Fusion ideal. Aquí hay un enlace a una descripción:

fusión ideal

Tenga en cuenta que esta descripción sugiere usar una estructura de búsqueda lineal o de montón (que es similar al algoritmo de Arun) para mantener el orden de las matrices de entrada. Desde que se publicó, me decidí a usar una búsqueda binaria que, como el método de almacenamiento dinámico, es O (MlogN) donde M es el número total de elementos en todas las matrices de entrada y N es el número de matrices de entrada. Por supuesto, con N = 3, una búsqueda lineal funcionará tan bien como una búsqueda binaria y es más fácil de codificar.

Simplemente inserte el elemento mínimo de todas las matrices. El siguiente programa C ++ 14 lo hará (para N matrices), y dudo que cualquier otro algoritmo sea más rápido si fusionamos solo unas pocas matrices.

#include
#include
#include
usando el espacio de nombres estándar;

// ———————————————————————-
// T es un contenedor con iteradores, begin () y end (), que contiene
// un tipo que implementa: operador bool <()
// T podría ser, por ejemplo, el vector
//
// Se devuelve el contenedor ordenado
// ———————————————————————-
plantilla
T merge_sorted (const vector & x)
{
typedef typename T :: const_iterator siter;

vector beg_it (x.size ()),
end_it (x.size ());

transform (x.begin (), x.end (), beg_it.begin (), [] (auto & v) {return v.begin ();});
transform (x.begin (), x.end (), end_it.begin (), [] (auto & v) {return v.end ();});

auto ptr_compare = [] (auto a, auto b) {return * a <* b; };
T fuera;

mientras que (1)
{
// encuentra el elemento min, max y su distancia
auto min = min_element (beg_it.begin (), beg_it.end (), ptr_compare);
out.insert (out.end (), ** min);
auto cur = min – beg_it.begin ();
if (++ (* min) == end_it [cur])
{
end_it.erase (end_it.begin () + cur);
beg_it.erase (beg_it.begin () + cur);
if (beg_it.empty ())
rotura;
}
}
regresar
}

int main ()
{
vector > v {
{3, 55, 64, 99, 223, 656, 669, 998},
{2, 5, 66, 87, 123, 126, 155, 232, 666, 673},
{1, 4, 55, 75, 76, 87, 102, 199, 200}
};

auto res = merge_sorted (v);
para (auto x: res)
printf (“% d \ n”, x);
}