Merge n listas vinculadas classificadas usando Min Heap

Aqui, o objetivo é se beneficiar do fato de que uma pilha de torrez. A entrada inicial de cada lista vinculada é o menor elemento em sua lista correspondente, pois, nesta técnica, todas as listas vinculadas já são classificadas. Aproveitamos essa circunstância criando um min-heap fora do membro inicial de cada lista vinculada. O menor elemento é então obtido extraindo o elemento superior (raiz) do min-heap. Temos o menor elemento em todas as listas vinculadas fazendo isso. O próximo elemento é então adicionado ao min-heap depois que aumentamos o ponteiro da lista à qual o elemento recém-extraído pertence. Um novo elemento é retirado do Min-Heap, o ponteiro da lista vinculado que o contém é incrementado, e o elemento recém-pontual é então adicionado ao min-heap. Até que o min-heap esteja completamente vazio, esta operação é repetida. Lembre-se de que adicionamos continuamente os elementos que extraímos do min-heap para uma lista de resultados separada que estamos mantendo.

A flexibilidade do método é um benefício importante. Com alguns pequenos ajustes, essa abordagem também pode ser usada para combinar as matrizes N classificadas. Algumas das outras maneiras não conseguem fazer isso, mas essa abordagem é bem -sucedida mesmo quando todas as listas vinculadas não são do mesmo tamanho.

Algoritmo:

Vamos primeiro dar uma olhada no algoritmo dessa estratégia antes de usar um exemplo para esclarecê -lo.

1) Crie um min-heap e preencha-o com o primeiro item de cada uma das listas vinculadas "n".

2) Repita as seguintes ações até que o min-heap esteja completo vazio:

1. Remova o elemento do Min-Root Heap e inclua-o na lista de resultados.
2. Adicione o elemento ao min-heap se estiver na mesma lista vinculada e estiver ao lado do elemento que foi extraído anteriormente.

3) Retorne o endereço do nó da lista de resultados.

Para compreender melhor o método, vamos usar um exemplo. Digamos que as seguintes listagens vinculadas nos sejam fornecidas:

O elemento (1) desta pilha de torrez. Nesse caso, o item que foi estourado é da segunda lista vinculada. Como contém um item próximo (item 7), o segundo ponteiro da lista vinculado é modificado para se referir ao item 7 e o item 7 é adicionado ao min-heap. O elemento atual extraído 1 é adicionado à matriz de saída final.

O elemento inicial 2 é estampado e anexado à lista vinculada recém -formada. Assim, o ponteiro da terceira lista vinculado é alterado para apontar para o próximo elemento que é 7. Este elemento é adicionado ao min-heap porque 2 era um membro desta lista vinculada.

O número 4 é removido do min-heap e adicionado à lista vinculada, que é o resultado final da lista vinculada. Um novo elemento (6) é adicionado ao min-heap e o ponteiro da primeira lista vinculado é modificado para apontar para ela.

A lista vinculada resultante agora inclui o número 6 extraído 6. Como o elemento seis (6) foi anteriormente parte da primeira lista vinculada. Seu ponteiro agora está apontando para o seguinte elemento (8), e esse elemento é adicionado ao min-heap.

Mais uma vez, pegamos o nó raiz (7) e adicionamos ao min-heap. Enquanto o ponteiro da segunda lista vinculado é atualizado, nenhum novo elementos é adicionado ao min-heap porque não há nenhum na segunda lista vinculada.

Nesse caso, o número 7 da terceira lista vinculado é exibido do min-heap. As atualizações são feitas no ponteiro da terceira lista vinculada, e o valor 29 é adicionado à pilha mínima.

Desta vez, vamos colocar o número 8, então movemos o ponteiro para a primeira lista vinculada. Novamente, nenhum novo elementos é adicionado ao min-heap porque não há nenhum na primeira lista vinculada.

O último elemento restante no min-heap, número 29, é removido. O ponteiro para a terceira lista vinculado é atualizado. Mas como já não há novos elementos na lista, nenhum é adicionado.

Agora que o min-heap está vazio, podemos usar a lista vinculada que foi gerada como a lista vinculada mesclada. Esta é a forma final da lista vinculada que é produzida por este algoritmo.

Entenda os conceitos com código e imagem

Temos três listas vinculadas, como mostrado no seguinte:

Observação: No início, a pilha min está vazia.

Adicionamos os primeiros elementos de todas as listas vinculadas na pilha.

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

se (Array [i] != Nulo)
MINNHEAP.push (matriz [i]);

Criamos uma lista vinculada resultante, como mostrado na imagem:

Nó da estrutura *HeadNode = newNode (0);
Nó da estrutura *tempnode = headNode;

O loop while é executado porque o MINHEAP não está vazio (tamanho = 3 (> 0)).

Aqui, extraímos o elemento superior da pilha e a atribuímos ao tempnode resultante.

Elemento superior (curr) = 2
Nó da estrutura* curr = MINHEAP.principal();
MINNHEAP.pop ();
tempnode-> próximo = curr;

Agora, neste código, alocamos o tempnode com toda a lista vinculada do elemento superior. O elemento 2 está incluído nos outros membros da lista conectada, como pode ser visto na imagem a seguir:

tempnode = tempnode-> próximo; Tempnode -> 2
curr -> 2

Então, na imagem anterior, podemos ver que o tempnode está apontando para o curr (elemento superior).

Agora, nesta etapa, temos que verificar se o elemento superior atual tem outro membro da lista vinculado ou não. Se ainda houver um membro, adicionamos esse elemento à pilha.

se (curr-> próximo != Nulo)
MINNHEAP.push (curr-> a seguir);

Adicionamos o elemento número 5 à pilha porque o elemento superior atual foi 2 e seu próximo elemento é 5.

Novamente, seguimos as etapas anteriores.

O loop while é executado porque o MINHEAP não está vazio (tamanho = 3 (> 0)). Aqui, extraímos o elemento superior da pilha e a atribuímos ao tempnode resultante.

Elemento superior (curr) = 3
Nó da estrutura* curr = MINHEAP.principal();
MINNHEAP.pop ();
tempnode-> próximo = curr;

Novamente, neste código, alocamos o tempnode com toda a lista vinculada do elemento superior. O elemento 3 está incluído nos outros membros da lista conectada, como pode ser visto na imagem a seguir:

tempnode = tempnode-> próximo; Tempnode -> 3
curr -> 3

Observação: A lista vinculada do elemento superior 2 anterior é substituído pela lista vinculada do novo membro superior.

Novamente, nesta etapa, verificamos se o elemento superior atual tem outro membro da lista vinculado ou não. Se ainda houver um membro, adicionamos esse elemento à pilha.

se (curr-> próximo != Nulo)
MINNHEAP.push (curr-> a seguir);

Adicionamos o elemento número 4 à pilha porque o elemento superior atual foi 3 e seu próximo elemento é 4.

Novamente, seguimos as etapas anteriores.

O loop while é executado porque o MINHEAP não está vazio (tamanho = 3 (> 0)).

Aqui, extraímos o elemento superior da pilha e a atribuímos ao tempnode resultante.

Elemento superior (curr) = 4
Nó da estrutura* curr = MINHEAP.principal();
MINNHEAP.pop ();
tempnode-> próximo = curr;

Novamente, neste código, alocamos o tempnode com toda a lista vinculada do elemento superior. O elemento 4 está incluído nos outros membros da lista conectada, como pode ser visto na imagem a seguir. E também, novamente, nesta etapa, verificamos se o elemento superior atual tem outro membro da lista vinculado ou não. Se ainda houver um membro, adicionamos esse elemento à pilha.

tempnode = tempnode-> próximo;
se (curr-> próximo != Nulo)
MINNHEAP.push (curr-> a seguir); Tempnode -> 4
curr -> 4

Adicionamos o elemento número 6 à pilha porque o elemento superior atual foi 4 e seu próximo elemento é 6.

Agora, o elemento 5 é inserido.

Tempnode -> 5
curr -> 5

Agora, o elemento 6 é inserido.

Tempnode -> 6
curr -> 6

Curr (6)-> Next == NULL porque nenhum elemento está disponível após o elemento 6. Então, nada é adicionado à pilha.

Agora, o elemento 7 é adicionado após o elemento 6.

Tempnode -> 7
curr -> 7

Agora, o elemento 8 é adicionado após o elemento 7.

Tempnode -> 8
curr -> 8

Agora, o elemento 9 é adicionado após o elemento 8.

Tempnode -> 9
Curr -> 9

Curr (9)-> Next == NULL porque nenhum elemento está disponível após o elemento 9. Então, nada é adicionado à pilha.

Finalmente, adicionamos o elemento 10 na lista.

Agora, a pilha está vazia. Então, o loop quebra e nós devolvemos o código do cabeçote.

Implementando o algoritmo de heap para mesclar as listas classificadas

#incluir
usando namespace std;
Nó da estrutura
int info;
Nó da estrutura*Em seguida;
;
Nó da estrutura*newNode (int info)
Nó da estrutura*new_node = new Node ();
new_node-> info = info;
new_node-> próximo = null;
returnnew_node;

// Função 'Compare' usada para construir
// Aumente a fila de prioridade
Struct Compare
operador bool () (
Nó da estrutura* a, nó de estrutura* b)
retornar a-> info> b-> info;

;
// Nesta função, vamos mesclar listas vinculadas classificadas em uma lista
Nó da estrutura* merge_n_sorted_linkedlists (nó struct* array [], int n)

// Priority_QueUe'MinhapH 'implementado com a função de comparação
Fila de prioridade MINNHEAP;
// Estamos empurrando todos os nós principais do
// Lista vinculada na pilha MINNHEAP
for (inti = 0; inext = curr;
tempnode = tempnode-> próximo;
// Verificando o membro da lista superior ainda disponível ORNOT
se (curr-> próximo!= Nulo)
// empurrando o próximo nó do nó superior para o Minhap
MINNHEAP.push (curr-> a seguir);
// Endereço do nó da cabeça da lista mesclada necessária
returnHeadNode-> Em seguida;

// Função para exibir a lista vinculada
Void DisplayMerGelinkedList (nó da estrutura* Head)
enquanto (cabeça != Null)
cout

int main ()
// N Número de listas vinculadas
int n = 3;
// Uma variedade de dicas que armazena os nós da lista da lista vinculada
Nó* array [n];
matriz [0] = newNode (2);
matriz [0]-> próximo = newNode (4);
matriz [0]-> próximo-> próximo = newNode (6);
Array [0]-> Next-> Next-> Next = newNode (8);
matriz [1] = newNode (3);
matriz [1]-> next = newNode (5);
matriz [1]-> próximo-> próximo = newNode (7);
Array [1]-> Next-> Next-> Next = newNode (9);
matriz [2] = newNode (1);
matriz [2]-> próximo = newNode (10);
matriz [2]-> próximo-> next = newNode (11);
matriz [2]-> próximo-> próximo-> next = newNode (12);
Nó da estrutura* head = merge_n_sorted_linkedlists (array, n);
displayMergelinkedList (cabeça);
return0;

Saída:

Conclusão

Aprendemos como combinar as listas vinculadas N classificadas em uma única lista vinculada neste artigo. Fornecemos um exemplo visual simples, utilizando a pilha min para ajudá -lo a compreender essa ideia. Depois disso, também explicamos usando código e gráficos. Como a pilha mínima era a base deste método, também tentamos descrever como ele funciona neste artigo. Este método tem uma complexidade de tempo de O (n.log (k)) onde n é o número de nós na lista e k é o número total de listas.