Fusionar n listas vinculadas ordenadas usando Min Heap

Aquí, el objetivo es beneficiarse del hecho de que un montón de raíz mínimo siempre devuelve al miembro más pequeño. La entrada inicial de cada lista vinculada es el elemento más pequeño en su lista correspondiente ya que, en esta técnica, todas las listas vinculadas ya están ordenadas. Aprovechamos esta circunstancia creando un montón de mínimo del miembro inicial de cada lista vinculada. Luego se obtiene el elemento más pequeño extrayendo el elemento superior (raíz) del mínimo-montón. Obtenemos el elemento más pequeño en todas las listas vinculadas haciendo esto. El siguiente elemento se agrega luego al Min-Weap después de aumentar el puntero a la lista a la que pertenece el elemento recién extraído. Se toma un nuevo elemento del Min-Heap, el puntero de la lista vinculada que lo contiene se incrementa, y el elemento recién puntiagudo se agrega al Min-Heap. Hasta que el Min-Heap esté completamente vacío, esta operación se repite. Tenga en cuenta que agregamos continuamente los elementos que extraemos del Min-Heap a una lista de resultados separada que estamos manteniendo.

La flexibilidad del método es un beneficio clave. Con algunos ajustes menores, este enfoque también se puede utilizar para combinar las matrices N ordenadas. Algunas de las otras formas no hacen esto, pero este enfoque tiene éxito incluso cuando todas las listas vinculadas no son del mismo tamaño.

Algoritmo:

Primero echemos un vistazo al algoritmo para esta estrategia antes de usar un ejemplo para aclararlo.

1) Cree un mínimo de tiempo y llénelo con el primer elemento de cada una de las listas vinculadas "n".

2) Repita las siguientes acciones hasta que el Min-Heap esté completo vacío:

1. Elimine el elemento del montón de raíz min-raít e incluya en la lista de resultados.
2. Agregue el elemento al Min-Heap si está en la misma lista vinculada y está al lado del elemento que se extrajo previamente.

3) Devuelva la dirección del nodo principal de la lista de resultados.

Para comprender mejor el método, usemos un ejemplo. Digamos que se nos proporcionan los siguientes listados vinculados:

El elemento (1) de este montón de raíz mínimo está explotado. En este caso, el elemento que apareció es de la segunda lista vinculada. Dado que contiene un elemento cercano (ítem 7), el puntero de la segunda lista vinculada se modifica para referirse al ítem 7, y el elemento 7 se agrega al mínimo-heap. El elemento extraído de corriente 1 se agrega a la matriz de salida final.

El elemento inicial que es 2 está explotado y agregado a la lista vinculada recién formada. Por lo tanto, el puntero de la tercera lista vinculada se cambia para apuntar al siguiente elemento que es 7. Este elemento se agrega al Min-Heap porque 2 era miembro de esta lista vinculada.

El número 4 se elimina del MIN-HeAP y se agrega a la lista vinculada, que es el resultado final de la lista vinculada. Se agrega un nuevo elemento (6) al Min-Heap, y el puntero de la primera lista vinculada se modifica para señalarlo.

La lista vinculada resultante ahora incluye el número 6 extraído. Dado que Element Six (6) fue anteriormente parte de la primera lista vinculada. Su puntero ahora apunta al siguiente elemento (8), y este elemento se agrega al Min-Heap.

Una vez más, tomamos el nodo raíz (7) y lo agregamos al montón de min. Mientras que el puntero a la segunda lista vinculada se actualiza, no se agregan nuevos elementos al MIN-Heap porque no hay ninguno en la segunda lista vinculada.

En este caso, el número 7 de la tercera lista vinculada se aparece desde el mínimo-heap. Las actualizaciones se realizan al puntero de la tercera lista vinculada, y el valor 29 se agrega al montón mínimo.

Esta vez, vamos a encontrar el número 8, entonces, movemos el puntero a la primera lista vinculada. Una vez más, no se agregan nuevos elementos al MIN-Heap porque no queda ninguno en la primera lista vinculada.

Se elimina el último elemento restante en el mínimo de tiempo 29. Se actualiza el puntero a la tercera lista vinculada. Pero dado que ya no hay elementos nuevos en la lista, no se agregan ninguno.

Ahora que el Min-Heap está vacío, podemos usar la lista vinculada que se generó como la lista vinculada fusionada. Esta es la forma final de la lista vinculada producida por este algoritmo.

Comprender los conceptos con código e imagen

Tenemos tres listas vinculadas como se muestra en lo siguiente:

Nota: Al comienzo, el montón mínimo está vacío.

Agregamos los primeros elementos de todas las listas vinculadas a la pila.

para (int i = 0; i < N; i++)

if (array [i] != Nulo)
minheap.push (matriz [i]);

Creamos una lista vinculada resultante como se muestra en la imagen:

struct node *headNode = newnode (0);
struct node *tempnode = headNode;

El bucle mientras se ejecuta porque el minheap no está vacío (tamaño = 3 (> 0)).

Aquí, extraemos el elemento superior de la pila y lo asignamos al tempnode resultante.

Elemento superior (Curr) = 2
nodo struct* curr = minheap.arriba();
minheap.estallido();
tempnode-> next = curs;

Ahora, en este código, asignamos el tempnode con toda la lista vinculada del elemento superior. El elemento 2 se incluye con los otros miembros de la lista conectada, como se puede ver en la siguiente imagen:

tempnode = tempnode-> next; tempnode -> 2
Curr -> 2

Entonces, en la imagen anterior, podemos ver que Tempnode apunta a Curr (elemento superior).

Ahora, en este paso, tenemos que verificar si el elemento superior actual tiene otro miembro de la lista vinculada o no. Si todavía hay un miembro, agregamos ese elemento al montón.

if (Curr-> Siguiente != Nulo)
minheap.push (curr-> next);

Agregamos el elemento número 5 a la pila porque el elemento superior actual era 2 y su siguiente elemento es 5.

Nuevamente, seguimos los pasos anteriores.

El bucle mientras se ejecuta porque Minheap no está vacío (tamaño = 3 (> 0)). Aquí, extraemos el elemento superior de la pila y lo asignamos al tempnode resultante.

Elemento superior (Curr) = 3
nodo struct* curr = minheap.arriba();
minheap.estallido();
tempnode-> next = curs;

Nuevamente, en este código, asignamos el tempnode con toda la lista vinculada del elemento superior. El elemento 3 se incluye con los otros miembros de la lista conectada, como se puede ver en la siguiente imagen:

tempnode = tempnode-> next; tempnode -> 3
Curr -> 3

Nota: La lista vinculada del elemento superior 2 actual previamente actual se sobrescribe mediante la lista vinculada del nuevo miembro superior.

Nuevamente, en este paso, verificamos si el elemento superior actual tiene otro miembro de la lista vinculada o no. Si todavía hay un miembro, agregamos ese elemento a la pila.

if (Curr-> Siguiente != Nulo)
minheap.push (curr-> next);

Agregamos el elemento número 4 a la pila porque el elemento superior actual era 3 y su siguiente elemento es 4.

Nuevamente, seguimos los pasos anteriores.

El bucle mientras se ejecuta porque el minheap no está vacío (tamaño = 3 (> 0)).

Aquí, extraemos el elemento superior de la pila y lo asignamos al tempnode resultante.

Elemento superior (Curr) = 4
nodo struct* curr = minheap.arriba();
minheap.estallido();
tempnode-> next = curs;

Nuevamente, en este código, asignamos el tempnode con toda la lista vinculada del elemento superior. El elemento 4 se incluye con los otros miembros de la lista conectada, como se puede ver en la siguiente imagen. Y también, nuevamente, en este paso, verificamos si el elemento superior actual tiene otro miembro de la lista vinculada o no. Si todavía hay un miembro, agregamos ese elemento a la pila.

tempnode = tempnode-> next;
if (Curr-> Siguiente != Nulo)
minheap.push (curr-> next); tempnode -> 4
Curr -> 4

Agregamos el elemento número 6 a la pila porque el elemento superior actual era 4 y su siguiente elemento es 6.

Ahora, el elemento 5 se inserta.

tempnode -> 5
Curr -> 5

Ahora, el elemento 6 está insertado.

tempnode -> 6
Curr -> 6

Curr (6)-> Next == nulo porque no hay elemento disponible después del elemento 6. Entonces, no se agrega nada al montón.

Ahora, el elemento 7 se agrega después del elemento 6.

tempnode -> 7
Curr -> 7

Ahora, el elemento 8 se agrega después del elemento 7.

tempnode -> 8
Curr -> 8

Ahora, el elemento 9 se agrega después del elemento 8.

Tempnode -> 9
Curr -> 9

Curr (9)-> Next == nulo porque no hay elemento disponible después del elemento 9. Entonces, no se agrega nada al montón.

Finalmente, agregamos el elemento 10 en la lista.

Ahora, el montón está vacío. Entonces, el bucle se rompe y devolvemos el nodo de cabeza.

Implementación del algoritmo de montón para fusionar las listas N ordenadas

#incluir
usando el espacio de nombres STD;
nodo de estructura
int info;
nodo de estructura*Siguiente;
;
struct node*newnode (int info)
struct node*new_node = new Node ();
new_node-> info = info;
new_node-> next = null;
returnnew_node;

// La función 'comparar' utilizada para construir
// Up de la cola de prioridad
struct compare
operador bool () (
struct nodo* a, nodo de estructura* b)
devolver a-> info> b-> info;

;
// En esta función, vamos a fusionar las listas vinculadas ordenadas en una lista
struct node* merge_n_sorted_linkedLists (struct node* array [], int n)

// priority_queue'minheap 'implementado con la función de comparación
prioridad_queue Minheap;
// estamos empujando todos los nodos de la cabeza del
// Lista vinculada a Minheap Stack
para (inti = 0; inext = curr;
tempnode = tempnode-> next;
// Comprobación de los mejores miembros de Listany todavía disponible Ornot
if (Curr-> Siguiente!= Nulo)
// empujando el siguiente nodo del nodo superior al minheap
minheap.push (curr-> next);
// Dirección del nodo principal de la lista fusionada requerida
returnheadnode-> next;

// función para mostrar la lista vinculada
void DisplayMerGelinkedList (Struct Node* Head)
mientras (cabeza != Nulo)
cout

int main ()
// n número de listas vinculadas
int n = 3;
// Una variedad de punteros que almacena los nodos de la cabeza de la lista vinculada
Nodo* matriz [n];
matriz [0] = newnode (2);
matriz [0]-> next = newnode (4);
matriz [0]-> next-> next = newnode (6);
matriz [0]-> next-> next-> next = newnode (8);
matriz [1] = newnode (3);
matriz [1]-> next = newnode (5);
matriz [1]-> next-> next = newnode (7);
matriz [1]-> next-> next-> next = newnode (9);
matriz [2] = newnode (1);
matriz [2]-> next = newnode (10);
matriz [2]-> next-> next = newnode (11);
matriz [2]-> next-> next-> next = newnode (12);
struct node* head = merge_n_sorted_linkedLists (Array, n);
DisplayMerGelinkedList (cabeza);
return0;

Producción:

Conclusión

Aprendimos a combinar las l listas vinculadas ordenadas en una sola lista vinculada ordenada en este artículo. Proporcionamos un ejemplo visual simple utilizando el montón MIN para ayudarlo a comprender esta idea. Después de eso, también lo explicamos usando código y gráficos. Dado que el montón mínimo era la base de este método, también intentamos describir cómo funciona en este artículo. Este método tiene una complejidad de tiempo de O (n.log (k)) donde n es el número de nodos en la lista, y k es el número total de listas.