PRIORITETSKÖ (DATASTRUKTURER) - HANDLEDNING FÖR DS

En prioritetskö är en abstrakt datatyp som beter sig på samma sätt som den normala kön förutom att varje element har en viss prioritet, dvs elementet med högst prioritet skulle komma först i en prioritetskö. Prioriteten för elementen i en prioritetskö kommer att avgöra i vilken ordning element tas bort från prioritetskön.

Prioritetskön stöder endast jämförbara element, vilket innebär att elementen antingen är ordnade i stigande eller fallande ordning.

abstrakt klass java

Anta till exempel att vi har några värden som 1, 3, 4, 8, 14, 22 infogade i en prioritetskö med en ordningsföljd som påtvingas värdena är från minst till störst. Därför skulle 1-numret ha högsta prioritet medan 22 kommer att ha lägst prioritet.

Egenskaper för en prioriterad kö

En prioritetskö är en förlängning av en kö som innehåller följande egenskaper:

Varje element i en prioritetskö har en viss prioritet kopplad till sig.
Ett element med högre prioritet kommer att raderas innan den lägre prioritet tas bort.
Om två element i en prioritetskö har samma prioritet kommer de att ordnas med FIFO-principen.

Låt oss förstå prioritetskön genom ett exempel.

Vi har en prioritetskö som innehåller följande värden:

1, 3, 4, 8, 14, 22

Alla värden är ordnade i stigande ordning. Nu kommer vi att observera hur prioritetskön kommer att se ut efter att ha utfört följande operationer:

opinionsundersökning():Denna funktion tar bort det högsta prioritetselementet från prioritetskön. I ovanstående prioritetskö har '1'-elementet högsta prioritet, så det kommer att tas bort från prioritetskön.add(2):Denna funktion kommer att infoga '2' element i en prioritetskö. Eftersom 2 är det minsta elementet bland alla siffror kommer det att få högsta prioritet.opinionsundersökning():Det kommer att ta bort elementet '2' från prioritetskön eftersom det har högsta prioritetskön.add(5):Det kommer att infoga 5 element efter 4 eftersom 5 är större än 4 och mindre än 8, så det kommer att få den tredje högsta prioriteten i en prioritetskö.

Typer av prioriterade köer

Det finns två typer av prioriterade köer:

Representation av prioriterad kö

Nu kommer vi att se hur man representerar prioritetskön genom en enkelriktad lista.

Vi kommer att skapa prioritetskön genom att använda listan nedan i vilken INFO listan innehåller dataelementen, PRN listan innehåller prioritetsnumren för varje dataelement som är tillgängligt i INFO list, och LINK innehåller i princip adressen till nästa nod.

Låt oss skapa prioriteringskön steg för steg.

java sort arraylist

I fallet med prioriterad kö anses lägre prioritetsnummer vara den högre prioriteten, dvs. lägre prioritetsnummer = högre prioritet.

Steg 1: I listan är lägre prioritetsnummer 1, vars datavärde är 333, så det kommer att infogas i listan som visas i diagrammet nedan:

Steg 2: Efter infogning av 333 har prioritet nummer 2 en högre prioritet, och datavärden associerade med denna prioritet är 222 och 111. Så, denna data kommer att infogas baserat på FIFO-principen; därför läggs 222 till först och sedan 111.

Steg 3: Efter att ha infogat elementen i prioritet 2 är nästa högre prioritetsnummer 4 och dataelement associerade med 4 prioritetsnummer är 444, 555, 777. I detta fall skulle element infogas baserat på FIFO-principen; därför läggs 444 till först, sedan 555 och sedan 777.

Steg 4: Efter att ha infogat elementen i prioritet 4 är nästa högre prioritetsnummer 5, och värdet associerat med prioritet 5 är 666, så det kommer att infogas i slutet av kön.

Implementering av Priority Queue

Prioritetskön kan implementeras på fyra sätt som inkluderar arrayer, länkad lista, heapdatastruktur och binärt sökträd. Högdatastrukturen är det mest effektiva sättet att implementera prioritetskön, så vi kommer att implementera prioritetskön med hjälp av en högdatastruktur i detta ämne. Nu förstår vi först anledningen till att heap är det mest effektiva sättet bland alla andra datastrukturer.

Analys av komplexitet med hjälp av olika implementeringar

Genomförande	Lägg till	Avlägsna	titt
Länkad lista	O(1)	På)	På)
Binär hög	O(logga)	O(logga)	O(1)
Binärt sökträd	O(logga)	O(logga)	O(1)

Vad är Heap?

En heap är en trädbaserad datastruktur som bildar ett komplett binärt träd och uppfyller heap-egenskapen. Om A är en modernod till B, så ordnas A med avseende på noden B för alla noder A och B i en hög. Det betyder att värdet på den överordnade noden kan vara mer än eller lika med värdet på den underordnade noden, eller så kan värdet på den överordnade noden vara mindre än eller lika med värdet på den underordnade noden. Därför kan vi säga att det finns två typer av högar:

simkort isatt men ingen tjänst android

Båda högarna är den binära högen, eftersom var och en har exakt två underordnade noder.

Prioriterade köoperationer

De vanliga operationerna som vi kan utföra på en prioriterad kö är infogning, radering och titt. Låt oss se hur vi kan behålla högdatastrukturen.

Infoga elementet i en prioritetskö (max heap)

Om vi infogar ett element i en prioritetskö kommer det att flyttas till den tomma luckan genom att titta uppifrån och ned och från vänster till höger.

Om elementet inte är på rätt plats jämförs det med modernoden; om det upptäcks ur funktion byts element. Denna process fortsätter tills elementet placeras i rätt position.

Ta bort minimielementet från prioritetskön

Som vi vet att i en maxhög är det maximala elementet rotnoden. När vi tar bort rotnoden skapar den en tom plats. Det senast infogade elementet kommer att läggas till i denna tomma plats. Sedan jämförs detta element med barnnoderna, dvs vänster-barn och höger barn, och byter med den minsta av de två. Den fortsätter att röra sig ner i trädet tills högegenskapen återställs.

Applikationer av prioriterad kö

Följande är tillämpningarna av prioritetskön:

Den används i Dijkstras algoritm för kortaste vägen.
Det används i prims algoritm
Det används i datakomprimeringstekniker som Huffman-kod.
Det används i högsort.
Det används också i operativsystem som prioriteringsschemaläggning, lastbalansering och avbrottshantering.

Program för att skapa prioritetskön med den binära maxhögen.

 #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

Vad är en prioriterad kö?