TechCodeview

Prioriteettijono on abstrakti tietotyyppi, joka käyttäytyy samalla tavalla kuin normaali jono, paitsi että jokaisella elementillä on jokin prioriteetti, eli korkeimman prioriteetin omaava elementti tulee prioriteettijonon ensimmäiseksi. Prioriteettijonon elementtien prioriteetti määrittää järjestyksen, jossa elementit poistetaan prioriteettijonosta.

Prioriteettijono tukee vain vertailukelpoisia elementtejä, mikä tarkoittaa, että elementit on järjestetty joko nousevaan tai laskevaan järjestykseen.

mysql luo käyttäjä

Oletetaan esimerkiksi, että meillä on joitain arvoja, kuten 1, 3, 4, 8, 14, 22, lisättynä prioriteettijonoon, ja arvot ovat järjestettävissä pienimmästä suurimpaan. Siksi numerolla 1 on korkein prioriteetti, kun taas numerolla 22 on alhaisin prioriteetti.

Priority-jonon ominaisuudet

Prioriteettijono on jonon laajennus, joka sisältää seuraavat ominaisuudet:

• Jokaiseen prioriteettijonon elementtiin liittyy jokin prioriteetti.
• Elementti, jolla on korkeampi prioriteetti, poistetaan ennen alemman prioriteetin poistamista.
• Jos kahdella prioriteettijonon elementillä on sama prioriteetti, ne järjestetään FIFO-periaatteella.

Ymmärretään prioriteettijono esimerkin kautta.

Meillä on prioriteettijono, joka sisältää seuraavat arvot:

1, 3, 4, 8, 14, 22

Kaikki arvot on järjestetty nousevaan järjestykseen. Nyt tarkkailemme, miltä prioriteettijono näyttää seuraavien toimintojen suorittamisen jälkeen:

kysely():Tämä toiminto poistaa korkeimman prioriteetin elementin prioriteettijonosta. Yllä olevassa prioriteettijonossa elementillä 1 on korkein prioriteetti, joten se poistetaan prioriteettijonosta.lisää(2):Tämä toiminto lisää '2'-elementin prioriteettijonoon. Koska 2 on pienin elementti kaikista numeroista, se saa korkeimman prioriteetin.kysely():Se poistaa '2'-elementin prioriteettijonosta, koska sillä on korkein prioriteettijono.lisää(5):Se lisää 5 elementin 4:n jälkeen, koska 5 on suurempi kuin 4 ja pienempi kuin 8, joten se saa kolmanneksi korkeimman prioriteetin prioriteettijonossa.

Prioriteettijonojen tyypit

Ensisijaisia ​​jonoja on kahdenlaisia:

Nousevassa järjestyksessä prioriteettijono:Nousevassa järjestyksessä prioriteettijonossa alempi prioriteettinumero annetaan korkeampana prioriteettina prioriteetissa. Esimerkiksi otamme numerot 1 - 5 nousevaan järjestykseen, kuten 1,2,3,4,5; siksi pienin luku, eli 1, annetaan korkeimmaksi prioriteetiksi prioriteettijonossa.
Laskevan järjestyksen prioriteettijono:Laskevassa prioriteettijonossa korkeampi prioriteettinumero annetaan korkeampana prioriteettina prioriteetissa. Esimerkiksi otamme numerot 1:stä 5:een järjestettynä laskevaan järjestykseen, kuten 5, 4, 3, 2, 1; siksi suurin numero, ts. 5, annetaan korkeimmaksi prioriteetiksi prioriteettijonossa.

Prioriteettijonon esitys

Nyt näemme, kuinka prioriteettijono esitetään yksisuuntaisen luettelon kautta.

Luomme prioriteettijonon käyttämällä alla olevaa luetteloa, jossa TIEDOT luettelo sisältää tietoelementit, PRN luettelo sisältää kunkin tietoelementin prioriteettinumerot, jotka ovat käytettävissä TIEDOT lista, ja LINK sisältää periaatteessa seuraavan solmun osoitteen.

Luodaan prioriteettijono askel askeleelta.

tostring java

Prioriteettijonon tapauksessa alhaisempi prioriteettinumero katsotaan korkeammaksi prioriteetiksi, ts. pienempi prioriteettinumero = korkeampi prioriteetti.

Vaihe 1: Listassa alemman prioriteetin numero on 1, jonka data-arvo on 333, joten se lisätään luetteloon alla olevan kaavion mukaisesti:

Vaihe 2: Lisäyksen 333 jälkeen prioriteettinumerolla 2 on korkeampi prioriteetti, ja tähän prioriteettiin liittyvät data-arvot ovat 222 ja 111. Joten tämä data lisätään FIFO-periaatteen perusteella; siksi 222 lisätään ensin ja sitten 111.

Vaihe 3: Prioriteetin 2 elementtien lisäämisen jälkeen seuraava korkeampi prioriteettinumero on 4 ja 4 prioriteettinumeroon liittyvät tietoelementit ovat 444, 555, 777. Tässä tapauksessa elementit lisättäisiin FIFO-periaatteella; siksi ensin lisätään 444, sitten 555 ja sitten 777.

Vaihe 4: Kun prioriteetin 4 elementit on lisätty, seuraava korkeampi prioriteettinumero on 5 ja prioriteettiin 5 liittyvä arvo on 666, joten se lisätään jonon loppuun.

Priority Queuen käyttöönotto

Prioriteettijono voidaan toteuttaa neljällä tavalla, joihin kuuluvat taulukot, linkitetty lista, keon tietorakenne ja binäärihakupuu. Keon tietorakenne on tehokkain tapa toteuttaa prioriteettijono, joten toteutamme prioriteettijonon käyttämällä keon tietorakennetta tässä aiheessa. Nyt ymmärrämme ensin syyn siihen, miksi kasa on tehokkain tapa kaikkien muiden tietorakenteiden joukossa.

Monimutkaisuuden analyysi erilaisilla toteutuksilla

Mikä on Heap?

Keko on puupohjainen tietorakenne, joka muodostaa täydellisen binääripuun ja täyttää keon ominaisuuden. Jos A on B:n pääsolmu, niin A on järjestetty suhteessa solmuun B kaikille kasan solmuille A ja B. Se tarkoittaa, että pääsolmun arvo voi olla suurempi tai yhtä suuri kuin alisolmun arvo, tai emosolmun arvo voi olla pienempi tai yhtä suuri kuin alisolmun arvo. Siksi voimme sanoa, että kasoja on kahdenlaisia:

Max kasa:Suurin kaso on kasa, jossa pääsolmun arvo on suurempi kuin alisolmujen arvo.
Minimi kasa:Minimikeko on kasa, jossa pääsolmun arvo on pienempi kuin alisolmujen arvo.

Molemmat kasat ovat binäärikekoja, koska kummallakin on täsmälleen kaksi alisolmua.

Prioriteettijonotoiminnot

Yleisimmät toiminnot, joita voimme suorittaa prioriteettijonossa, ovat lisäys, poisto ja kurkistus. Katsotaanpa, kuinka voimme ylläpitää keon tietorakennetta.

Elementin lisääminen prioriteettijonoon (enintään kasa)

Jos lisäämme elementin prioriteettijonoon, se siirtyy tyhjään paikkaan katsomalla ylhäältä alas ja vasemmalta oikealle.

Jos elementti ei ole oikeassa paikassa, sitä verrataan pääsolmuun; jos se havaitaan epäkunnossa, elementit vaihdetaan. Tämä prosessi jatkuu, kunnes elementti on asetettu oikeaan asentoon.

Poistetaan vähimmäiselementti prioriteettijonosta

Kuten tiedämme, että maksimikeossa suurin elementti on juurisolmu. Kun poistamme juurisolmun, se luo tyhjän paikan. Viimeksi lisätty elementti lisätään tähän tyhjään paikkaan. Sitten tätä elementtiä verrataan lapsisolmuihin, eli vasen-lapsi ja oikea lapsi, ja vaihdetaan pienemmän kanssa. Se liikkuu alas puussa, kunnes kasan omaisuus on palautettu.

Priority-jonon sovellukset

Seuraavat ovat prioriteettijonon sovellukset:

merkkijono java

• Sitä käytetään Dijkstran lyhimmän polun algoritmissa.
• Sitä käytetään primin algoritmissa
• Sitä käytetään tietojen pakkaustekniikoissa, kuten Huffman-koodissa.
• Sitä käytetään kasalajittelussa.
• Sitä käytetään myös käyttöjärjestelmissä, kuten prioriteettien ajoituksessa, kuormituksen tasapainottamisessa ja keskeytyskäsittelyssä.

Ohjelma luomaan prioriteettijonon binaarisen maksimikeon avulla.

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