PRIORITETSKØ (DATASTRUKTURER)

En prioritetskø er en abstrakt datatype, der opfører sig på samme måde som den normale kø, bortset fra at hvert element har en vis prioritet, dvs. elementet med den højeste prioritet vil komme først i en prioritetskø. Prioriteten af elementerne i en prioritetskø vil bestemme rækkefølgen, hvori elementer fjernes fra prioritetskøen.

Prioritetskøen understøtter kun sammenlignelige elementer, hvilket betyder, at elementerne enten er arrangeret i stigende eller faldende rækkefølge.

execvp

Antag for eksempel, at vi har nogle værdier som 1, 3, 4, 8, 14, 22 indsat i en prioritetskø med en rækkefølge pålagt værdierne er fra mindst til størst. Derfor vil 1-tallet have den højeste prioritet, mens 22 vil have den laveste prioritet.

Karakteristika for en prioriteret kø

En prioritetskø er en udvidelse af en kø, der indeholder følgende egenskaber:

Hvert element i en prioritetskø har en eller anden prioritet tilknyttet.
Et element med den højere prioritet vil blive slettet før sletningen af den lavere prioritet.
Hvis to elementer i en prioritetskø har samme prioritet, vil de blive arrangeret efter FIFO-princippet.

Lad os forstå prioritetskøen gennem et eksempel.

Vi har en prioritetskø, der indeholder følgende værdier:

1, 3, 4, 8, 14, 22

Alle værdier er arrangeret i stigende rækkefølge. Nu vil vi observere, hvordan prioritetskøen vil se ud efter at have udført følgende handlinger:

afstemning():Denne funktion fjerner det højeste prioritetselement fra prioritetskøen. I ovenstående prioritetskø har '1'-elementet den højeste prioritet, så det vil blive fjernet fra prioritetskøen.tilføje(2):Denne funktion vil indsætte '2' element i en prioritetskø. Da 2 er det mindste element blandt alle tallene, vil det opnå den højeste prioritet.afstemning():Det vil fjerne '2'-elementet fra prioritetskøen, da det har den højeste prioritetskø.tilføje(5):Det vil indsætte 5 element efter 4, da 5 er større end 4 og mindre end 8, så det vil opnå den tredje højeste prioritet i en prioritetskø.

Typer af prioriteret kø

Der er to typer prioritetskøer:

Repræsentation af prioriteret kø

Nu vil vi se, hvordan man repræsenterer prioritetskøen gennem en envejsliste.

Vi vil oprette prioritetskøen ved at bruge listen nedenfor, hvori INFO listen indeholder dataelementerne, PRN listen indeholder prioritetsnumrene for hvert dataelement, der er tilgængeligt i INFO liste, og LINK indeholder grundlæggende adressen på den næste node.

Lad os oprette prioritetskøen trin for trin.

java sort arraylist

I tilfælde af prioritetskø betragtes lavere prioritetsnummer som den højere prioritet, dvs. lavere prioritet nummer = højere prioritet.

Trin 1: På listen er lavere prioritetsnummer 1, hvis dataværdi er 333, så det vil blive indsat i listen som vist i nedenstående diagram:

Trin 2: Efter indsættelse af 333 har prioritet nummer 2 en højere prioritet, og dataværdier forbundet med denne prioritet er 222 og 111. Så disse data vil blive indsat baseret på FIFO-princippet; derfor tilføjes 222 først og derefter 111.

Trin 3: Efter indsættelse af elementerne i prioritet 2 er det næste højere prioritetsnummer 4, og dataelementer, der er knyttet til 4 prioritetsnumre, er 444, 555, 777. I dette tilfælde vil elementer blive indsat baseret på FIFO-princippet; derfor tilføjes 444 først, derefter 555 og derefter 777.

Trin 4: Efter indsættelse af elementerne i prioritet 4 er det næste højere prioritetsnummer 5, og værdien forbundet med prioritet 5 er 666, så det vil blive indsat i slutningen af køen.

Implementering af Priority Queue

Prioritetskøen kan implementeres på fire måder, der inkluderer arrays, sammenkædet liste, heap-datastruktur og binært søgetræ. Heap-datastrukturen er den mest effektive måde at implementere prioritetskøen på, så vi vil implementere prioritetskøen ved hjælp af en heap-datastruktur i dette emne. Nu forstår vi først grunden til, at heap er den mest effektive måde blandt alle de andre datastrukturer.

Analyse af kompleksitet ved hjælp af forskellige implementeringer

Implementering	tilføje	Fjerne	kig
Linket liste	O(1)	På)	På)
Binær bunke	O(logn)	O(logn)	O(1)
Binært søgetræ	O(logn)	O(logn)	O(1)

Hvad er Heap?

En heap er en træbaseret datastruktur, der danner et komplet binært træ, og som opfylder heap-egenskaben. Hvis A er en forældreknude til B, så er A ordnet i forhold til knudepunktet B for alle knudepunkter A og B i en heap. Det betyder, at værdien af den overordnede node kan være mere end eller lig med værdien af den underordnede node, eller værdien af den overordnede node kan være mindre end eller lig med værdien af den underordnede node. Derfor kan vi sige, at der er to typer dynger:

minimax algoritme

Begge dynger er den binære hob, da hver har præcis to underordnede noder.

Prioriterede køoperationer

De almindelige handlinger, som vi kan udføre på en prioriteret kø, er indsættelse, sletning og kig. Lad os se, hvordan vi kan vedligeholde heap-datastrukturen.

Indsættelse af elementet i en prioriteret kø (max heap)

Hvis vi indsætter et element i en prioritetskø, vil det flytte til den tomme plads ved at se fra top til bund og venstre mod højre.

Hvis elementet ikke er på det korrekte sted, sammenlignes det med den overordnede node; hvis det er fundet ude af drift, byttes elementer. Denne proces fortsætter, indtil elementet er placeret i en korrekt position.

Fjernelse af minimumselementet fra prioritetskøen

Som vi ved, at i en max heap er det maksimale element rodknuden. Når vi fjerner rodnoden, opretter den en tom slot. Det sidst indsatte element vil blive tilføjet i denne tomme plads. Derefter sammenlignes dette element med børneknuderne, dvs. venstre-barn og højre barn, og swap med den mindste af de to. Den bliver ved med at bevæge sig ned i træet, indtil bunkeejendommen er genoprettet.

Ansøgninger af prioriteret kø

Følgende er applikationerne i prioritetskøen:

Det bruges i Dijkstra's korteste vej-algoritme.
Det bruges i prims algoritme
Det bruges i datakomprimeringsteknikker som Huffman-kode.
Det bruges i heap sortering.
Det bruges også i operativsystemer som prioriteringsplanlægning, belastningsbalancering og afbrydelseshåndtering.

Program til at oprette prioritetskøen ved hjælp af den binære max-bunke.

 #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])>

TechCodeview

Hvad er en prioriteret kø?