Slå sammen og sorterte koblede lister ved hjelp av Min Heap

Her er målet å dra nytte av det faktum at en Min-Root Heap alltid returnerer det minste medlemmet. Den første oppføringen til hver koblede liste er det minste elementet i den tilsvarende listen, siden alle de koblede listene allerede er sortert i denne teknikken. Vi drar nytte av denne omstendigheten ved å opprette en min-heap av det første medlemmet av hver koblede liste. Det minste elementet oppnås deretter ved å trekke ut det øverste elementet (roten) til Min-Heap. Vi får det minste elementet på tvers av alle koblede lister ved å gjøre dette. Det neste elementet blir deretter lagt til Min-Heap etter at vi har økt pekeren til listen som det nyutformede elementet tilhører. Et nytt element er hentet fra Min-Heap, den koblede listepekeren som inneholder den økes, og det nypekte elementet blir deretter lagt til Min-Heap. Inntil min-heapen er helt tom, gjentas denne operasjonen. Husk at vi kontinuerlig legger til elementene som vi trekker ut fra Min-Heap til en egen resultatliste som vi holder på.

Metodens fleksibilitet er en viktig fordel. Med noen få mindre justeringer kan denne tilnærmingen også brukes til å kombinere N -sorterte matriser. Noen av de andre måtene klarer ikke å gjøre dette, men denne tilnærmingen lykkes selv når alle koblede lister ikke er i samme størrelse.

Algoritme:

La oss først se på algoritmen for denne strategien før vi bruker et eksempel for å avklare den.

1) Lag en min-heap og fyll den med det første elementet fra hver av de "n" koblede listene.

2) Gjenta følgende handlinger frem til Min-Heap er fullstendig tom:

1. Fjern min-roothautens element og inkluder det i resultatlisten.
2. Legg elementet i min-heap hvis det er i den samme koblede listen og er ved siden av elementet som tidligere ble trukket ut.

3) Returner resultatlistenes hodebueadresse.

For å forstå metoden bedre, la oss bruke et eksempel. La oss si at følgende koblede oppføringer blir gitt oss:

Elementet (1) av denne min-roothaugen er poppet. I dette tilfellet er varen som ble poppet fra den andre koblede listen. Siden den inneholder et nærliggende element (punkt 7), blir den andre koblede listens peker modifisert for å referere til punkt 7, og punkt 7 blir lagt til Min-Heap. Det nåværende ekstraherte elementet 1 legges til den endelige utgangsarrayen.

Det opprinnelige elementet som er 2 blir poppet og lagt til den nydannede koblede listen. Dermed blir pekeren til den tredje koblede listen endret til pek til neste element som er 7. Dette elementet legges til Min-Heap fordi 2 var medlem av denne koblede listen.

Nummer 4 fjernes fra Min-Heap og legges til den koblede listen som er den endelige koblede listeutfallet. Et nytt element (6) legges til Min-Heap, og pekeren til den første koblede listen blir endret for å peke på den.

Den resulterende koblede listen inkluderer nå den ekstraherte nummer 6. Siden element seks (6) tidligere var en del av den første koblede listen. Pekeren peker nå på følgende element (8), og dette elementet legges til Min-Heap.

Nok en gang tar vi rotnoden (7) og legger den til i min-heap. Mens pekeren til den andre koblede listen er oppdatert, blir ingen nye elementer lagt til Min-Heap fordi det ikke er noen i den andre koblede listen.

I dette tilfellet blir nummer 7 fra den tredje koblede listen poppet fra Min-Heap. Oppdateringer blir gjort til pekeren til den tredje koblede listen, og verdien 29 legges til minimumshaugen.

Denne gangen skal vi poppe nummer 8 da, vi flytter pekeren inn i den første koblede listen. Igjen blir ingen nye elementer lagt til Min-Heap fordi det ikke er noen igjen i den første koblede listen.

Det siste gjenværende elementet i Min-Heap, nummer 29, fjernes. Pekeren til den tredje koblede listen er oppdatert. Men siden det allerede er noen nye elementer på listen, er ingen lagt til.

Nå som Min-Heap er tom, kan vi bruke den koblede listen som ble generert som den sammenslåtte koblede listen. Dette er den endelige formen for den koblede listen som er produsert av denne algoritmen.

Forstå konseptene med kode og bilde

Vi har tre koblede lister som vist i følgende:

Merk: I starten er min haugen tom.

Vi legger til de første elementene i alle de koblede listene i bunken.

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

if (matrise [i] != Null)
Minheap.Push (Array [i]);

Vi oppretter en resulterende koblet liste som vist på bildet:

struct node *headnode = newNode (0);
struct node *tempnode = headnode;

Mens sløyfe utføres fordi Minheap ikke er tom (størrelse = 3 (> 0)).

Her trekker vi ut toppelementet fra stabelen og tildeler det til den resulterende tempnoden.

Toppelement (curr) = 2
struct node* curr = minheap.topp();
Minheap.pop ();
tempnode-> neste = curr;

Nå, i denne koden, tildeler vi tempnoden med hele den koblede listen over det øverste elementet. Element 2 er inkludert i de andre tilkoblede listemedlemmene, som det kan sees i følgende bilde:

tempnode = tempnode-> neste; tempnode -> 2
Curr -> 2

Så i det forrige bildet kan vi se at tempnode peker på Curr (toppelementet).

Nå, i dette trinnet, må vi sjekke om det nåværende toppelementet har et annet lenket listemedlem eller ikke. Hvis det fremdeles er medlem, legger vi til det elementet til haugen.

if (curr-> neste != Null)
Minheap.Push (Curr-> Neste);

Vi legger til elementet nummer 5 til stabelen fordi det nåværende toppelementet var 2 og dets neste element er 5.

Igjen, vi følger de foregående trinnene.

Mens sløyfe utføres fordi Minheap ikke er tom (størrelse = 3 (> 0)). Her trekker vi ut toppelementet fra stabelen og tildeler det til den resulterende tempnoden.

Toppelement (curr) = 3
struct node* curr = minheap.topp();
Minheap.pop ();
tempnode-> neste = curr;

Igjen, i denne koden, tildeler vi tempnoden med hele den koblede listen over det øverste elementet. Element 3 er inkludert i de andre tilkoblede listemedlemmene, som det kan sees i følgende bilde:

tempnode = tempnode-> neste; tempnode -> 3
Curr -> 3

Merk: Den koblede listen over det tidligere nåværende toppelementet 2 blir overskrevet av den koblede listen over det nye toppmedlemmet.

Igjen, i dette trinnet, sjekker vi om det nåværende toppelementet har et annet lenket listemedlem eller ikke. Hvis det fremdeles er medlem, legger vi til det elementet til stabelen.

if (curr-> neste != Null)
Minheap.Push (Curr-> Neste);

Vi legger til elementet nummer 4 til stabelen fordi det nåværende toppelementet var 3 og dets neste element er 4.

Igjen, vi følger de foregående trinnene.

Mens sløyfe utføres fordi Minheap ikke er tom (størrelse = 3 (> 0)).

Her trekker vi ut toppelementet fra stabelen og tildeler det til den resulterende tempnoden.

Toppelement (curr) = 4
struct node* curr = minheap.topp();
Minheap.pop ();
tempnode-> neste = curr;

Igjen, i denne koden, tildeler vi tempnoden med hele den koblede listen over det øverste elementet. Element 4 er inkludert i de andre tilkoblede listemedlemmene, som det kan sees i følgende bilde. Og også, igjen, i dette trinnet, sjekker vi om det nåværende toppelementet har et annet lenket listemedlem eller ikke. Hvis det fremdeles er medlem, legger vi til det elementet til stabelen.

tempnode = tempnode-> neste;
if (curr-> neste != Null)
Minheap.Push (Curr-> Neste); tempnode -> 4
Curr -> 4

Vi legger til elementet nummer 6 til stabelen fordi det nåværende toppelementet var 4 og dets neste element er 6.

Nå settes element 5 inn.

tempnode -> 5
Curr -> 5

Nå settes element 6 inn.

tempnode -> 6
Curr -> 6

Curr (6)-> Neste == NULL fordi ingen element er tilgjengelig etter elementet 6. Så ingenting er lagt til i haugen.

Nå blir element 7 lagt til etter element 6.

tempnode -> 7
Curr -> 7

Nå blir element 8 lagt til etter element 7.

tempnode -> 8
Curr -> 8

Nå blir element 9 lagt til etter element 8.

tempnode -> 9
Curr -> 9

Curr (9)-> Neste == NULL fordi ingen element er tilgjengelig etter elementet 9. Så ingenting er lagt til i haugen.

Til slutt legger vi til elementet 10 på listen.

Nå er haugen tom. Så sløyfen går i stykker og vi returnerer headnode.

Implementering av Heap -algoritmen for å slå sammen N -sorterte lister

#inkludere
ved hjelp av navneområdet STD;
struct node
int info;
struct node*Neste;
;
struct node*newNode (int info)
struct node*new_node = new node ();
new_node-> info = info;
new_node-> neste = null;
returnnew_node;

// 'sammenligne' funksjon som brukes til å bygge
// opp prioriteringskøen
struktur sammenligne
booloperatør () (
struct node* a, struct node* b)
Return A-> Info> B-> Info;

;
// I denne funksjonen skal vi slå sammen og sorterte koblede lister i en liste
struct node* Merge_n_sorted_linkedLists (struct node* array [], int n)

// Priority_queue'minheap 'implementert med sammenligningsfunksjonen
Priority_queue Minheap;
// Vi skyver alle hodeknuter av
// Linked List i Minheap Stack
for (inti = 0; inext = curr;
tempnode = tempnode-> neste;
// Kontrollere Top Listany -medlem fremdeles tilgjengelig ornot
if (curr-> neste!= Null)
// skyve neste node med toppnode inn i minheapen
Minheap.Push (Curr-> Neste);
// Adresse på hodeknute på den nødvendige sammenslåtte listen
returheadnode-> neste;

// Funksjon for å vise den koblede listen
void displayMergelinkedList (struct node* head)
mens (hode != Null)
cout

int main ()
// N Antall koblede lister
int n = 3;
// en rekke pekere som lagrer den koblede listenes hodeknuter
Node* array [n];
Array [0] = newNode (2);
Array [0]-> neste = newNode (4);
Array [0]-> next-> next = newNode (6);
Array [0]-> next-> next-> next = newNode (8);
Array [1] = newNode (3);
Array [1]-> neste = newNode (5);
Array [1]-> next-> next = newNode (7);
Array [1]-> next-> next-> next = newNode (9);
Array [2] = newNode (1);
Array [2]-> neste = 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 (hode);
retur0;

Produksjon:

Konklusjon

Vi lærte hvordan vi kan kombinere n -sorterte koblede lister i en enkelt sortert koblet liste i denne artikkelen. Vi ga et enkelt visuelt eksempel ved å bruke Min -haugen for å hjelpe deg med å forstå denne ideen. Etter det forklarte vi det også ved hjelp av kode og grafikk. Siden minimumshaugen var grunnlaget for denne metoden, forsøkte vi også å beskrive hvordan den fungerer i denne artikkelen. Denne metoden har en tidskompleksitet av O (n.Logg (k)) hvor n er antall noder i listen, og k er det totale antallet lister.