Unisci elenchi collegati ordinati utilizzando Min Heap

Qui, l'obiettivo è beneficiare del fatto che un heap con radice minimo restituisce sempre il membro più piccolo. La voce iniziale di ciascun elenco collegato è l'elemento più piccolo nell'elenco corrispondente poiché, in questa tecnica, tutti gli elenchi collegati sono già ordinati. Sfruttiamo questa circostanza creando un minimo dal membro iniziale di ogni elenco collegato. L'elemento più piccolo viene quindi ottenuto estraendo l'elemento superiore (radice) del minimo. Otteniamo l'elemento più piccolo in tutte le liste collegate facendo questo. L'elemento successivo viene quindi aggiunto al minimo dopo aver aumentato il puntatore all'elenco a cui appartiene l'elemento appena estratto. Un nuovo elemento viene tratto dal Min-Heap, il puntatore dell'elenco collegato che contiene viene incrementato e l'elemento appena appuntito viene quindi aggiunto al Min-Heap. Fino a quando il minimo non è completamente vuoto, questa operazione viene ripetuta. Tieni presente che aggiungiamo continuamente gli elementi che estraggiamo dal Min-Heap a un elenco di risultati separato che stiamo mantenendo.

La flessibilità del metodo è un vantaggio chiave. Con alcune lievi aggiustamenti, questo approccio può anche essere usato per combinare gli array di N ordinati. Alcuni degli altri modi non riescono a farlo, ma questo approccio ha successo anche quando tutte le liste collegate non hanno le stesse dimensioni.

Algoritmo:

Diamo prima un'occhiata all'algoritmo per questa strategia prima di usare un esempio per chiarirlo.

1) Crea un minimo e riempilo con il primo elemento da ciascuna delle liste collegate "N".

2) Ripeti le seguenti azioni fino a quando il minimo non è completo:

1. Rimuovere l'elemento del mucchio di root e includerlo nell'elenco dei risultati.
2. Aggiungi l'elemento al minimo se si trova nella stessa lista collegata ed è vicino all'elemento che è stato precedentemente estratto.

3) Restituisci l'indirizzo del nodo della testa dell'elenco dei risultati.

Per comprendere meglio il metodo, usiamo un esempio. Diciamo che ci vengono forniti i seguenti elenchi collegati:

L'elemento (1) di questo mucchio di root viene visualizzato. In questo caso, l'articolo che è stato visualizzato è dalla seconda lista collegata. Poiché contiene un elemento vicino (elemento 7), il puntatore dell'elenco del secondo collegato viene modificato per fare riferimento all'articolo 7 e l'articolo 7 viene aggiunto al minimo. L'elemento estratto di corrente 1 viene aggiunto all'array di uscita finale.

L'elemento iniziale che è 2 viene visualizzato e aggiunto all'elenco collegato di recente formazione. Pertanto, il puntatore del terzo elenco collegato viene modificato per indicare l'elemento successivo che è 7. Questo elemento viene aggiunto al minimo perché 2 era un membro di questo elenco collegato.

Il numero 4 viene rimosso dal Min-heap e aggiunto all'elenco collegato che è il risultato finale dell'elenco collegato. Un nuovo elemento (6) viene aggiunto al minimo e il puntatore del primo elenco collegato viene modificato per indicarlo.

L'elenco collegato a risultante ora include il numero estratto 6. Poiché l'elemento sei (6) era precedentemente parte del primo elenco collegato. Il suo puntatore ora punta al seguente elemento (8) e questo elemento viene aggiunto al minimo.

Ancora una volta, prendiamo il nodo radice (7) e lo aggiungiamo al minuto. Mentre il puntatore al secondo elenco collegato viene aggiornato, non vengono aggiunti nuovi elementi al minimo perché non ce ne sono nella seconda lista collegata.

In questo caso, il numero 7 della terza lista collegata viene visualizzato dal Min-Heap. Gli aggiornamenti vengono effettuati al puntatore del terzo elenco collegato e il valore 29 viene aggiunto al mucchio minimo.

Questa volta, faremo un pop il numero 8 quindi, spostiamo il puntatore nella prima lista collegata. Ancora una volta, nessun nuovo elemento viene aggiunto al minimo perché non ci sono rimasti nella prima lista collegata.

L'ultimo elemento rimasto nel minimo, il numero 29, viene rimosso. Il puntatore al terzo elenco collegato viene aggiornato. Ma poiché non ci sono già nuovi elementi nell'elenco, nessuno viene aggiunto.

Ora che il minimo è vuoto, possiamo usare l'elenco collegato che è stato generato come elenco collegato unita. Questa è la forma finale dell'elenco collegato prodotto da questo algoritmo.

Comprendi i concetti con codice e immagine

Abbiamo tre elenchi collegati come mostrato da segue:

Nota: All'inizio, il mucchio di min è vuoto.

Aggiungiamo i primi elementi di tutte le liste collegate nello stack.

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

if (array [i] != Null)
Minheap.push (array [i]);

Creiamo un elenco collegato risultante come mostrato nell'immagine:

Struct Node *HeadNode = newNode (0);
Struct Node *tempNode = HeadNode;

Il ciclo while viene eseguito perché MinHeap non è vuoto (dimensione = 3 (> 0)).

Qui, estraggiamo l'elemento superiore dallo stack e lo assegniamo al tempnode risultante.

Elemento superiore (Curr) = 2
nodo struct* curr = MinHeap.superiore();
Minheap.pop();
tempnode-> next = curr;

Ora, in questo codice, allochiamo il tempnode con l'intero elenco collegato dell'elemento superiore. L'elemento 2 è incluso con gli altri membri dell'elenco connesso, come si può vedere nella seguente immagine:

tempNode = tempNode-> Next; tempnode -> 2
Curr -> 2

Quindi, nell'immagine precedente, possiamo vedere che tempnode punta al Curr (Top Element).

Ora, in questo passaggio, dobbiamo verificare se l'elemento superiore corrente ha un altro membro dell'elenco collegato o no. Se c'è ancora un membro, aggiungiamo quell'elemento al mucchio.

if (Curr-> Next != Null)
Minheap.Push (Curr-> Next);

Aggiungiamo l'elemento numero 5 allo stack perché l'elemento superiore corrente era 2 e il suo prossimo elemento è 5.

Ancora una volta, seguiamo i passaggi precedenti.

Il ciclo while viene eseguito perché MinHeap non è vuoto (dimensione = 3 (> 0)). Qui, estraggiamo l'elemento superiore dallo stack e lo assegniamo al tempnode risultante.

Elemento superiore (Curr) = 3
nodo struct* curr = MinHeap.superiore();
Minheap.pop();
tempnode-> next = curr;

Ancora una volta, in questo codice, allochiamo il tempnode con l'intero elenco collegato dell'elemento superiore. L'elemento 3 è incluso con gli altri membri dell'elenco connesso, come si può vedere nella seguente immagine:

tempNode = tempNode-> Next; tempnode -> 3
Curr -> 3

Nota: L'elenco collegato dell'elemento top 2 precedentemente corrente è sovrascritto dall'elenco collegato del nuovo membro superiore.

Ancora una volta, in questo passaggio, controlliamo se l'elemento superiore corrente ha un altro membro dell'elenco collegato o no. Se c'è ancora un membro, aggiungiamo quell'elemento allo stack.

if (Curr-> Next != Null)
Minheap.Push (Curr-> Next);

Aggiungiamo l'elemento numero 4 allo stack perché l'elemento superiore corrente era 3 e il suo prossimo elemento è 4.

Ancora una volta, seguiamo i passaggi precedenti.

Il ciclo while viene eseguito perché MinHeap non è vuoto (dimensione = 3 (> 0)).

Qui, estraggiamo l'elemento superiore dallo stack e lo assegniamo al tempnode risultante.

Elemento superiore (Curr) = 4
nodo struct* curr = MinHeap.superiore();
Minheap.pop();
tempnode-> next = curr;

Ancora una volta, in questo codice, allochiamo il tempnode con l'intero elenco collegato dell'elemento superiore. L'elemento 4 è incluso con gli altri membri dell'elenco connesso, come si può vedere nella seguente immagine. E anche, ancora una volta, in questo passaggio, controlliamo se l'elemento superiore corrente ha un altro membro dell'elenco collegato o no. Se c'è ancora un membro, aggiungiamo quell'elemento allo stack.

tempNode = tempNode-> Next;
if (Curr-> Next != Null)
Minheap.Push (Curr-> Next); tempnode -> 4
Curr -> 4

Aggiungiamo l'elemento numero 6 allo stack perché l'elemento superiore corrente era 4 e il suo prossimo elemento è 6.

Ora, l'elemento 5 viene inserito.

tempnode -> 5
Curr -> 5

Ora, l'elemento 6 viene inserito.

tempnode -> 6
Curr -> 6

Curr (6)-> Next == Null perché nessun elemento è disponibile dopo l'elemento 6. Quindi, nulla viene aggiunto al mucchio.

Ora, l'elemento 7 viene aggiunto dopo l'elemento 6.

tempnode -> 7
Curr -> 7

Ora, l'elemento 8 viene aggiunto dopo l'elemento 7.

tempnode -> 8
Curr -> 8

Ora, l'elemento 9 viene aggiunto dopo l'elemento 8.

tempnode -> 9
Curr -> 9

Curr (9)-> Next == Null perché nessun elemento è disponibile dopo l'elemento 9. Quindi, nulla viene aggiunto al mucchio.

Infine, aggiungiamo l'elemento 10 nell'elenco.

Ora, il mucchio è vuoto. Quindi, il ciclo si rompe e restituiamo il dono.

Implementazione dell'algoritmo heap per la fusione degli elenchi Normed

#includere
Utilizzo dello spazio dei nomi std;
nodo struct
Info int;
nodo struct*Next;
;
Struct Node*newnode (int info)
Struct node*new_node = new node ();
new_node-> info = info;
new_node-> next = null;
returnnew_node;

// Funzione 'Confronta' utilizzata per la costruzione
// su la coda prioritaria
struct confronta
Bool Operator () (
nodo struct* a, nodo struct* b)
restituisce a-> info> b-> info;

;
// In questa funzione, uniremo gli elenchi collegati ordinati in un elenco
Struct Node* Merge_n_Sorted_LinkedLists (struct Node* Array [], int n)

// priority_queue'minheap "implementato con la funzione di confronto
priorità_queue MinHeap;
// Stiamo spingendo tutti i nodi di testa del
// Elenco collegato allo stack di MinHeap
per (INTI = 0; INEXT = Curr;
tempNode = tempNode-> Next;
// Controllando il membro di alto livello ancora disponibile ORNOT
if (Curr-> Next!= Null)
// spingendo il nodo successivo del nodo superiore nel MinHeap
Minheap.Push (Curr-> Next);
// Indirizzo del nodo principale dell'elenco unito richiesto
returnheadnode-> next;

// funzione per visualizzare l'elenco collegato
void DisplayMerGelinkEdList (Struct Node* Head)
mentre (testa != Null)
cout

int main ()
// N Numero di elenchi collegati
int n = 3;
// Una matrice di puntatori che memorizza i nodi della testa dell'elenco collegato
Nodo* array [n];
array [0] = newnode (2);
array [0]-> next = newnode (4);
array [0]-> next-> next = newnode (6);
array [0]-> next-> next-> next = newnode (8);
array [1] = newnode (3);
array [1]-> next = newnode (5);
array [1]-> next-> next = newnode (7);
Array [1]-> Next-> Next-> Next = newnode (9);
array [2] = newnode (1);
array [2]-> next = newnode (10);
array [2]-> next-> next = newnode (11);
Array [2]-> Next-> Next-> Next = newnode (12);
Struct Node* head = Merge_n_Sorted_LinkedLists (array, n);
DisplayMerGelinkEdList (testa);
return0;

Produzione:

Conclusione

Abbiamo imparato come combinare gli elenchi collegati in un unico elenco collegato in questo articolo. Abbiamo fornito un semplice esempio visivo utilizzando il mucchio di min per aiutarti a comprendere questa idea. Dopodiché, l'abbiamo anche spiegato usando codice e grafica. Poiché il mucchio minimo era il fondamento di questo metodo, abbiamo anche tentato di descrivere come funziona in questo articolo. Questo metodo ha una complessità temporale di O (n.log (k)) dove n è il numero di nodi nell'elenco e k è il numero totale di elenchi.