TechCodeview

Prioritetinė eilė yra abstraktus duomenų tipas, kuris veikia panašiai kaip įprasta eilė, išskyrus tai, kad kiekvienas elementas turi tam tikrą prioritetą, t. Prioritetinės eilės elementų prioritetas nulems, kokia tvarka elementai pašalinami iš prioritetinės eilės.

Prioritetinė eilė palaiko tik palyginamus elementus, o tai reiškia, kad elementai yra išdėstyti didėjančia arba mažėjančia tvarka.

dvejetainiai medžių tipai

Pavyzdžiui, tarkime, kad kai kurios reikšmės, pvz., 1, 3, 4, 8, 14, 22, įterptos į prioritetinę eilę, o reikšmių tvarka yra nuo mažiausios iki didžiausios. Todėl 1 skaičius turėtų didžiausią prioritetą, o 22 - mažiausią prioritetą.

Prioritetinės eilės charakteristikos

Prioritetinė eilė yra eilės plėtinys, turintis šias charakteristikas:

• Kiekvienas prioritetinės eilės elementas turi tam tikrą su juo susietą prioritetą.
• Aukštesnio prioriteto elementas bus ištrintas prieš ištrinant mažesnio prioriteto.
• Jei du elementai prioritetinėje eilėje turi tą patį prioritetą, jie bus išdėstyti FIFO principu.

Supraskime prioritetinę eilę per pavyzdį.

Turime prioritetinę eilę, kurioje yra šios reikšmės:

1, 3, 4, 8, 14, 22

Visos reikšmės yra išdėstytos didėjančia tvarka. Dabar stebėsime, kaip prioritetinė eilė atrodys atlikus šias operacijas:

apklausa ():Ši funkcija pašalins aukščiausio prioriteto elementą iš prioritetų eilės. Pirmiau nurodytoje prioriteto eilėje elementas „1“ turi didžiausią prioritetą, todėl jis bus pašalintas iš prioritetinės eilės.pridėti (2):Ši funkcija įterps elementą „2“ į prioritetinę eilę. Kadangi 2 yra mažiausias elementas tarp visų skaičių, tai jam bus suteiktas didžiausias prioritetas.apklausa ():Jis pašalins elementą „2“ iš prioritetinės eilės, nes jis turi aukščiausio prioriteto eilę.pridėti (5):Jis įterps 5 elementą po 4, nes 5 yra didesnis nei 4 ir mažesnis nei 8, todėl prioritetų eilėje jis gaus trečią aukščiausią prioritetą.

Prioritetinių eilių tipai

Yra dviejų tipų prioritetinės eilės:

Didėjančios eilės prioriteto eilė:Didėjančios eilės prioriteto eilėje mažesnis prioriteto numeris suteikiamas kaip didesnis prioritetas prioritete. Pavyzdžiui, paimame skaičius nuo 1 iki 5, išdėstytus didėjančia tvarka, pavyzdžiui, 1,2,3,4,5; todėl pirmenybės eilėje didžiausias prioritetas suteikiamas mažiausias skaičius, ty 1.
Mažėjančios eilės prioriteto eilė:Mažėjančios eilės prioriteto eilėje didesnis prioriteto numeris suteikiamas kaip didesnis prioritetas prioritete. Pavyzdžiui, paimame skaičius nuo 1 iki 5, išdėstytus mažėjančia tvarka, pvz., 5, 4, 3, 2, 1; todėl prioritetinėje eilėje didžiausias prioritetas suteikiamas didžiausias skaičius, ty 5.

Prioritetinės eilės vaizdavimas

Dabar pamatysime, kaip pateikti prioritetinę eilę per vienpusį sąrašą.

Prioritetinę eilę sukursime naudodami toliau pateiktą sąrašą, kuriame INFORMACIJA sąraše yra duomenų elementai, PRN Sąraše yra kiekvieno duomenų elemento, esančio sąraše, prioriteto numeriai INFORMACIJA sąrašą, o LINK iš esmės yra kito mazgo adresas.

Žingsnis po žingsnio kurkime prioritetinę eilę.

java rūšiavimo masyvų sąrašas

Prioritetinės eilės atveju aukštesniu prioritetu laikomas mažesnis prioriteto numeris, t.y. mažesnis prioriteto skaičius = didesnis prioritetas.

1 žingsnis: Sąraše mažesnio prioriteto numeris yra 1, kurio duomenų reikšmė yra 333, todėl jis bus įtrauktas į sąrašą taip, kaip parodyta žemiau esančioje diagramoje:

2 žingsnis: Įvedus 333, prioritetas numeris 2 turi didesnį prioritetą, o su šiuo prioritetu susijusios duomenų reikšmės yra 222 ir 111. Taigi šie duomenys bus įterpiami FIFO principu; todėl pirmiausia bus pridėtas 222, o tada 111.

3 veiksmas: Įterpus 2 prioriteto elementus, kitas aukštesnis prioriteto numeris yra 4, o duomenų elementai, susiję su 4 prioriteto skaičiais, yra 444, 555, 777. Šiuo atveju elementai būtų įterpiami remiantis FIFO principu; todėl pirmiausia bus pridėta 444, tada 555 ir 777.

4 veiksmas: Įdėjus 4 prioriteto elementus, kitas didesnis prioriteto skaičius yra 5, o su 5 prioritetu susijusi reikšmė yra 666, todėl ji bus įterpiama eilės pabaigoje.

Prioritetinės eilės įgyvendinimas

Prioritetinė eilė gali būti įgyvendinta keturiais būdais, įskaitant masyvus, susietą sąrašą, krūvos duomenų struktūrą ir dvejetainį paieškos medį. Krūvos duomenų struktūra yra efektyviausias būdas įgyvendinti prioritetinę eilę, todėl šioje temoje prioritetinę eilę įgyvendinsime naudodami krūvos duomenų struktūrą. Dabar pirmiausia suprantame, kodėl krūva yra efektyviausias būdas tarp visų kitų duomenų struktūrų.

Sudėtingumo analizė naudojant skirtingus įgyvendinimus

Kas yra Krūva?

Krūva yra medžiu pagrįsta duomenų struktūra, kuri sudaro pilną dvejetainį medį ir atitinka krūvos savybę. Jei A yra pirminis B mazgas, tada A yra išdėstytas mazgo B atžvilgiu visuose krūvos mazguose A ir B. Tai reiškia, kad pirminio mazgo vertė gali būti didesnė arba lygi antrinio mazgo vertei, arba pirminio mazgo vertė gali būti mažesnė arba lygi antrinio mazgo vertei. Todėl galime pasakyti, kad yra dviejų tipų krūvos:

Java indeksas

Didžiausia krūva:Didžiausia krūva yra krūva, kurioje pirminio mazgo vertė yra didesnė už antrinių mazgų vertę.
Min. krūva:Minimali krūva yra krūva, kurioje pirminio mazgo vertė yra mažesnė už antrinių mazgų vertę.

Abi krūvos yra dvejetainė krūva, nes kiekviena turi tiksliai du antrinius mazgus.

Prioritetinės eilės operacijos

Įprastos operacijos, kurias galime atlikti prioritetinėje eilėje, yra įterpimas, trynimas ir peržiūra. Pažiūrėkime, kaip galime išlaikyti krūvos duomenų struktūrą.

Elemento įterpimas į prioritetinę eilę (maks. krūva)

Jei įterpsime elementą į prioritetinę eilę, jis bus perkeltas į tuščią vietą, žiūrint iš viršaus į apačią ir iš kairės į dešinę.

Jei elementas nėra tinkamoje vietoje, jis lyginamas su pirminiu mazgu; jei nustatoma, kad jis netvarkingas, elementai sukeičiami. Šis procesas tęsiasi tol, kol elementas yra tinkamoje padėtyje.

Pašalinamas minimalus elementas iš prioritetinės eilės

Kaip žinome, didžiausioje krūvoje didžiausias elementas yra šakninis mazgas. Kai pašaliname šakninį mazgą, jis sukuria tuščią lizdą. Paskutinis įterptas elementas bus įtrauktas į šią tuščią vietą. Tada šis elementas lyginamas su antriniais mazgais, t. y. kairysis vaikas ir dešinysis vaikas, ir pakeičiamas mažesniu iš dviejų. Jis juda žemyn medžiu, kol bus atkurta krūva.

Prioritetinės eilės programos

Toliau pateikiamos prioritetinės eilės programos:

• Jis naudojamas Dijkstra trumpiausio kelio algoritme.
• Jis naudojamas prim algoritme
• Jis naudojamas duomenų glaudinimo technikose, tokiose kaip Huffman kodas.
• Jis naudojamas krūvos rūšiavimui.
• Jis taip pat naudojamas operacinėse sistemose, tokiose kaip prioritetinis planavimas, apkrovos balansavimas ir pertraukimų tvarkymas.

Programa sukurti prioritetinę eilę naudojant dvejetainį maksimalų krūvą.

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