TechCodeview

Prioritātes rinda ir abstrakts datu tips, kas darbojas līdzīgi parastajai rindai, izņemot to, ka katram elementam ir noteikta prioritāte, t.i., elements ar augstāko prioritāti būtu prioritātes rindā pirmais. Prioritārās rindas elementu prioritāte noteiks secību, kādā elementi tiek noņemti no prioritārās rindas.

Prioritātes rinda atbalsta tikai salīdzināmus elementus, kas nozīmē, ka elementi ir sakārtoti augošā vai dilstošā secībā.

mylivecricket alternatīva

Piemēram, pieņemsim, ka prioritātes rindā ir ievietotas dažas vērtības, piemēram, 1, 3, 4, 8, 14, 22, un vērtību secība ir no mazākās līdz lielākajai. Tāpēc 1 skaitlim būs augstākā prioritāte, bet 22 būs zemākā prioritāte.

Prioritātes rindas raksturojums

Prioritātes rinda ir rindas paplašinājums, kas satur šādas īpašības:

• Katram prioritārās rindas elementam ir noteikta ar to saistīta prioritāte.
• Elements ar augstāku prioritāti tiks dzēsts pirms mazākās prioritātes dzēšanas.
• Ja diviem elementiem prioritātes rindā ir vienāda prioritāte, tie tiks sakārtoti, izmantojot FIFO principu.

Izpratīsim prioritāro rindu, izmantojot piemēru.

Mums ir prioritāra rinda, kurā ir šādas vērtības:

1, 3, 4, 8, 14, 22

Visas vērtības ir sakārtotas augošā secībā. Tagad mēs novērosim, kā prioritārā rinda izskatīsies pēc šādu darbību veikšanas:

aptauja ():Šī funkcija noņems augstākās prioritātes elementu no prioritārās rindas. Iepriekš minētajā prioritātes rindā elementam “1” ir augstākā prioritāte, tāpēc tas tiks noņemts no prioritārās rindas.pievienot (2):Šī funkcija prioritārajā rindā ievietos elementu “2”. Tā kā 2 ir mazākais elements starp visiem skaitļiem, tas iegūs augstāko prioritāti.aptauja ():Tas no prioritātes rindas noņems elementu “2”, jo tam ir augstākā prioritāte.pievienot (5):Tas ievietos 5 elementu pēc 4, jo 5 ir lielāks par 4 un mazāks par 8, tādējādi prioritāšu rindā tas iegūs trešo augstāko prioritāti.

Prioritātes rindas veidi

Ir divu veidu prioritārās rindas:

Prioritātes rinda augošā secībā:Prioritātes rindā augošā secībā zemāks prioritātes numurs tiek piešķirts kā augstāka prioritāte prioritātē. Piemēram, mēs ņemam skaitļus no 1 līdz 5, kas sakārtoti augošā secībā, piemēram, 1,2,3,4,5; tāpēc mazākais skaitlis, t.i., 1, tiek piešķirts kā augstākā prioritāte prioritātes rindā.
Dilstošā secībā prioritātes rinda:Prioritātes rindā dilstošā secībā augstāks prioritātes numurs tiek piešķirts kā augstāka prioritāte prioritātē. Piemēram, mēs ņemam skaitļus no 1 līdz 5, kas sakārtoti dilstošā secībā, piemēram, 5, 4, 3, 2, 1; tāpēc lielākais skaitlis, t.i., 5, tiek piešķirts kā augstākā prioritāte prioritātes rindā.

Prioritātes rindas attēlojums

Tagad mēs redzēsim, kā attēlot prioritāro rindu, izmantojot vienvirziena sarakstu.

Mēs izveidosim prioritāro rindu, izmantojot tālāk norādīto sarakstu, kurā INFORMĀCIJA sarakstā ir datu elementi, PRN saraksts satur katra pieejamā datu elementa prioritātes numurus INFORMĀCIJA saraksts, un LINK pamatā ir nākamā mezgla adrese.

Soli pa solim izveidosim prioritāro rindu.

java kārtošanas masīvu saraksts

Prioritātes rindas gadījumā zemāks prioritātes numurs tiek uzskatīts par augstāku prioritāti, t.i., zemāks prioritātes numurs = augstāka prioritāte.

1. darbība: Sarakstā zemākas prioritātes numurs ir 1, kura datu vērtība ir 333, tāpēc tas tiks ievietots sarakstā, kā parādīts zemāk esošajā diagrammā:

2. darbība: Pēc 333 ievietošanas prioritātes numurs 2 ir ar augstāku prioritāti, un ar šo prioritāti saistītās datu vērtības ir 222 un 111. Tātad šie dati tiks ievietoti, pamatojoties uz FIFO principu; tāpēc vispirms tiks pievienots 222 un pēc tam 111.

3. darbība: Pēc 2. prioritātes elementu ievietošanas nākamais augstākais prioritātes numurs ir 4 un datu elementi, kas saistīti ar 4 prioritātes numuriem, ir 444, 555, 777. Šajā gadījumā elementi tiktu ievietoti pēc FIFO principa; tāpēc vispirms tiks pievienoti 444, pēc tam 555 un pēc tam 777.

4. darbība: Pēc 4. prioritātes elementu ievietošanas nākamais augstākais prioritātes numurs ir 5, un ar 5. prioritāti saistītā vērtība ir 666, tāpēc tā tiks ievietota rindas beigās.

Prioritātes rindas ieviešana

Prioritātes rindu var ieviest četros veidos, kas ietver masīvus, saistīto sarakstu, kaudzes datu struktūru un bināro meklēšanas koku. Kaudzes datu struktūra ir visefektīvākais veids, kā ieviest prioritāro rindu, tāpēc šajā tēmā prioritāro rindu ieviesīsim, izmantojot kaudzes datu struktūru. Tagad vispirms mēs saprotam iemeslu, kāpēc kaudze ir visefektīvākais veids starp visām pārējām datu struktūrām.

Sarežģītības analīze, izmantojot dažādas realizācijas

Kas ir kaudze?

Kaudze ir uz koku balstīta datu struktūra, kas veido pilnīgu bināro koku un atbilst kaudzes īpašībai. Ja A ir B vecākmezgls, tad A tiek sakārtots attiecībā pret mezglu B visiem kaudzes mezgliem A un B. Tas nozīmē, ka vecākmezgla vērtība var būt lielāka vai vienāda ar pakārtotā mezgla vērtību, vai vecākmezgla vērtība var būt mazāka vai vienāda ar pakārtotā mezgla vērtību. Tāpēc mēs varam teikt, ka ir divu veidu kaudzes:

Maksimālā kaudze:Maksimālā kaudze ir kaudze, kurā vecākmezgla vērtība ir lielāka par pakārtoto mezglu vērtību.
Minimālā kaudze:Minimālā kaudze ir kaudze, kurā vecākmezgla vērtība ir mazāka par pakārtoto mezglu vērtību.

Abas kaudzes ir binārā kaudze, jo katrā ir tieši divi pakārtotie mezgli.

Prioritārās rindas darbības

Kopējās darbības, ko varam veikt prioritārā rindā, ir ievietošana, dzēšana un apskate. Apskatīsim, kā mēs varam uzturēt kaudzes datu struktūru.

Elementa ievietošana prioritārā rindā (maks. kaudze)

Ja mēs ievietosim elementu prioritārā rindā, tas tiks pārvietots uz tukšo slotu, skatoties no augšas uz leju un no kreisās uz labo pusi.

kā lasīt json failu

Ja elements neatrodas pareizā vietā, tas tiek salīdzināts ar vecākmezglu; ja tiek konstatēts, ka tas nav kārtībā, elementi tiek apmainīti. Šis process turpinās, līdz elements tiek novietots pareizā stāvoklī.

Minimālā elementa noņemšana no prioritārās rindas

Kā mēs zinām, ka maksimālajā kaudzē maksimālais elements ir saknes mezgls. Kad mēs noņemam saknes mezglu, tas izveido tukšu slotu. Šajā tukšajā slotā tiks pievienots pēdējais ievietotais elements. Pēc tam šo elementu salīdzina ar pakārtotajiem mezgliem, t.i., kreiso bērnu un labo bērnu, un apmaina ar mazāko no diviem. Tas turpina virzīties lejup pa koku, līdz tiek atjaunots kaudzes īpašums.

Prioritātes rindas lietojumprogrammas

Šīs ir prioritārās rindas lietojumprogrammas:

• To izmanto Dijkstra īsākā ceļa algoritmā.
• To izmanto prim algoritmā
• To izmanto datu saspiešanas metodēs, piemēram, Huffman kodā.
• To izmanto kaudzes šķirošanā.
• To izmanto arī operētājsistēmās, piemēram, prioritāšu plānošanā, slodzes līdzsvarošanā un pārtraukumu apstrādē.

Programma, lai izveidotu prioritāro rindu, izmantojot bināro maksimālo kaudzi.

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