TechCodeview

En prioritetskø er en abstrakt datatype som oppfører seg på samme måte som den vanlige køen, bortsett fra at hvert element har en viss prioritet, det vil si at elementet med høyest prioritet vil komme først i en prioritetskø. Prioriteten til elementene i en prioritetskø vil bestemme rekkefølgen elementer fjernes fra prioritetskøen.

Prioritetskøen støtter kun sammenlignbare elementer, noe som betyr at elementene enten er ordnet i stigende eller synkende rekkefølge.

execvp

Anta for eksempel at vi har noen verdier som 1, 3, 4, 8, 14, 22 satt inn i en prioritert kø med en rekkefølge pålagt verdiene er fra minst til størst. Derfor vil 1-tallet ha høyest prioritet mens 22 vil ha lavest prioritet.

Kjennetegn på en prioritert kø

En prioritetskø er en utvidelse av en kø som inneholder følgende egenskaper:

• Hvert element i en prioritetskø har en prioritet knyttet til seg.
• Et element med høyere prioritet vil bli slettet før sletting av lavere prioritet.
• Hvis to elementer i en prioritetskø har samme prioritet, vil de ordnes etter FIFO-prinsippet.

La oss forstå prioritetskøen gjennom et eksempel.

Vi har en prioritert kø som inneholder følgende verdier:

1, 3, 4, 8, 14, 22

Alle verdiene er ordnet i stigende rekkefølge. Nå vil vi observere hvordan prioritetskøen vil se ut etter å ha utført følgende operasjoner:

avstemming():Denne funksjonen vil fjerne det høyeste prioriterte elementet fra prioritetskøen. I prioritetskøen ovenfor har '1'-elementet høyest prioritet, så det vil bli fjernet fra prioritetskøen.legg til(2):Denne funksjonen vil sette inn '2' element i en prioritert kø. Siden 2 er det minste elementet blant alle tallene, vil det få høyeste prioritet.avstemming():Den vil fjerne '2'-elementet fra prioritetskøen ettersom den har høyest prioritetskø.legg til(5):Den vil sette inn 5 elementer etter 4 ettersom 5 er større enn 4 og mindre enn 8, så den vil oppnå tredje høyeste prioritet i en prioritetskø.

Typer prioritert kø

Det finnes to typer prioritetskøer:

Stigende rekkefølge prioritetskø:I stigende rekkefølge prioritetskø, er et lavere prioritet nummer gitt som en høyere prioritet i en prioritet. For eksempel tar vi tallene fra 1 til 5 ordnet i stigende rekkefølge som 1,2,3,4,5; derfor er det minste tallet, dvs. 1, gitt som høyeste prioritet i en prioritetskø.
Synkende rekkefølge prioritetskø:I synkende prioritetskø gis et høyere prioritetsnummer som en høyere prioritet i en prioritet. For eksempel tar vi tallene fra 1 til 5 ordnet i synkende rekkefølge som 5, 4, 3, 2, 1; derfor er det største tallet, dvs. 5, gitt som høyeste prioritet i en prioritetskø.

Representasjon av prioritert kø

Nå skal vi se hvordan vi representerer prioritetskøen gjennom en enveisliste.

Vi vil opprette prioritetskøen ved å bruke listen nedenfor der INFO listen inneholder dataelementene, PRN listen inneholder prioritetsnumrene for hvert dataelement som er tilgjengelig i INFO liste, og LINK inneholder i utgangspunktet adressen til neste node.

La oss lage prioritetskøen trinn for trinn.

java sortering arraylist

I tilfellet med prioritert kø, anses lavere prioritetsnummer som den høyeste prioritet, dvs. lavere prioritet nummer = høyere prioritet.

Trinn 1: I listen er nedre prioritetsnummer 1, hvis dataverdi er 333, så det vil bli satt inn i listen som vist i diagrammet nedenfor:

Steg 2: Etter innsetting av 333 har prioritet nummer 2 en høyere prioritet, og dataverdier assosiert med denne prioriteten er 222 og 111. Så disse dataene vil bli satt inn basert på FIFO-prinsippet; derfor legges 222 til først og deretter 111.

Trinn 3: Etter å ha satt inn elementene i prioritet 2, er det neste høyere prioritetsnummer 4 og dataelementer assosiert med 4 prioritetsnumre er 444, 555, 777. I dette tilfellet vil elementer bli satt inn basert på FIFO-prinsippet; derfor legges 444 til først, deretter 555 og deretter 777.

Trinn 4: Etter å ha satt inn elementene i prioritet 4, er det neste høyere prioritetstallet 5, og verdien knyttet til prioritet 5 er 666, så det vil bli satt inn på slutten av køen.

Implementering av Priority Queue

Prioritetskøen kan implementeres på fire måter som inkluderer arrays, koblet liste, heapdatastruktur og binært søketre. Heap-datastrukturen er den mest effektive måten å implementere prioritetskøen på, så vi vil implementere prioritetskøen ved å bruke en heap-datastruktur i dette emnet. Nå forstår vi først grunnen til at heap er den mest effektive måten blant alle de andre datastrukturene.

Analyse av kompleksitet ved hjelp av ulike implementeringer

Hva er Heap?

En heap er en trebasert datastruktur som danner et komplett binært tre, og tilfredsstiller heap-egenskapen. Hvis A er en overordnet node til B, er A ordnet i forhold til noden B for alle nodene A og B i en haug. Det betyr at verdien av den overordnede noden kan være mer enn eller lik verdien av den underordnede noden, eller verdien til den overordnede noden kan være mindre enn eller lik verdien til den underordnede noden. Derfor kan vi si at det er to typer hauger:

snu strengen i java

Maks haug:Maks haugen er en haug der verdien til den overordnede noden er større enn verdien til undernodene.
Min haug:Min-heapen er en haug der verdien til den overordnede noden er mindre enn verdien til undernodene.

Begge haugene er den binære haugen, siden hver har nøyaktig to underordnede noder.

Prioriterte køoperasjoner

De vanlige operasjonene vi kan utføre på en prioritert kø er innsetting, sletting og kikk. La oss se hvordan vi kan opprettholde haugdatastrukturen.

Sette inn elementet i en prioritert kø (maks haug)

Hvis vi setter inn et element i en prioritert kø, vil det flytte til det tomme sporet ved å se fra topp til bunn og venstre mot høyre.

Hvis elementet ikke er på riktig sted, sammenlignes det med overordnet node; hvis det er funnet i ustand, byttes elementer. Denne prosessen fortsetter til elementet er plassert i riktig posisjon.

Fjerner minimumselementet fra prioritetskøen

Som vi vet at i en maks haug, er det maksimale elementet rotnoden. Når vi fjerner rotnoden, skaper den et tomt spor. Det sist innsatte elementet vil bli lagt til i dette tomme sporet. Deretter sammenlignes dette elementet med barnetnodene, dvs. venstre-barn og høyre barn, og byttes med den minste av de to. Den fortsetter å bevege seg nedover treet til haugeiendommen er gjenopprettet.

Søknader av prioritert kø

Følgende er applikasjonene for prioritetskøen:

• Den brukes i Dijkstras korteste vei-algoritme.
• Den brukes i prims algoritme
• Den brukes i datakomprimeringsteknikker som Huffman-kode.
• Den brukes i haugsortering.
• Den brukes også i operativsystemer som prioriteringsplanlegging, lastbalansering og avbruddshåndtering.

Program for å lage prioritetskøen ved å bruke den binære maks-haugen.

 #include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i &gt; 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong>  </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>