A prioriteettijono on eräänlainen jono, joka järjestää elementit niiden prioriteettiarvojen perusteella. Elementit, joilla on korkeampi prioriteettiarvo, haetaan tyypillisesti ennen elementtejä, joilla on pienempi prioriteettiarvo.

Prioriteettijonossa jokaiselle elementille on liitetty prioriteettiarvo. Kun lisäät elementin jonoon, se lisätään paikkaan, joka perustuu sen prioriteettiarvoon. Jos esimerkiksi lisäät prioriteettijonoon elementin, jolla on korkea prioriteetti, se voidaan lisätä lähelle jonon etuosaa, kun taas matalan prioriteetin arvon omaava elementti voidaan lisätä lähelle takaosan.

On olemassa useita tapoja toteuttaa prioriteettijono, mukaan lukien taulukon, linkitetyn luettelon, keon tai binäärihakupuun käyttö. Jokaisella menetelmällä on omat etunsa ja haittansa, ja paras valinta riippuu sovelluksesi erityistarpeista.

Prioriteettijonoja käytetään usein reaaliaikaisissa järjestelmissä, joissa elementtien käsittelyjärjestyksellä voi olla merkittäviä seurauksia. Niitä käytetään myös algoritmeissa niiden tehokkuuden parantamiseksi, kuten Dijkstran algoritmi lyhimmän polun löytämiseen kaaviosta ja A*-hakualgoritmista polunhakua varten.

Prioriteettijonon ominaisuudet

Joten prioriteettijono on laajennus jonottaa seuraavilla ominaisuuksilla.

• Jokaiseen kohteeseen liittyy prioriteetti.
• Korkean prioriteetin elementti poistetaan jonosta ennen matalan prioriteetin elementtiä.
• Jos kahdella elementillä on sama prioriteetti, ne toimitetaan niiden järjestyksen mukaan jonossa.

Alla olevassa prioriteettijonossa elementillä, jolla on suurin ASCII-arvo, on korkein prioriteetti. Elementit, joilla on korkeampi prioriteetti, tarjotaan ensin.

Miten prioriteetti asetetaan prioriteettijonon elementeille?

Prioriteettijonossa etusijaa määritettäessä otetaan yleensä huomioon elementin arvo.

Esimerkiksi korkeimman arvon omaavalle elementille annetaan korkein prioriteetti ja pienimmän arvon omaavalle elementille alhaisin prioriteetti. Voidaan käyttää myös käänteistä tapausta, eli pienimmän arvon omaavalle elementille voidaan antaa korkein prioriteetti. Myös prioriteetti voidaan määrittää tarpeidemme mukaan.

Prioriteettijonon toiminnot:

Tyypillinen prioriteettijono tukee seuraavia toimintoja:

1) Lisäys prioriteettijonoon

Kun uusi elementti lisätään prioriteettijonoon, se siirtyy tyhjään paikkaan ylhäältä alas ja vasemmalta oikealle. Jos elementti ei kuitenkaan ole oikeassa paikassa, sitä verrataan pääsolmuun. Jos elementti ei ole oikeassa järjestyksessä, elementit vaihdetaan. Vaihtoprosessi jatkuu, kunnes kaikki elementit ovat oikeissa paikoissa.

2) Poisto prioriteettijonossa

Kuten tiedät, maksimikeossa suurin elementti on juurisolmu. Ja se poistaa elementin, jolla on suurin prioriteetti ensin. Siten poistat juurisolmun jonosta. Tämä poistaminen luo tyhjän paikan, joka täytetään edelleen uudella lisäyksellä. Sitten se vertaa äskettäin lisättyä elementtiä kaikkiin jonon sisällä oleviin elementteihin keon invariantin säilyttämiseksi.

3) Kurkista prioriteettijonoon

Tämä toiminto auttaa palauttamaan maksimielementin Max-keosta tai minimielementin Min-keosta poistamatta solmua prioriteettijonosta.

Prioriteettijonon tyypit:

1) Nousevan järjestyksen prioriteettijono

Kuten nimestä voi päätellä, nousevassa järjestyksessä prioriteettijonossa alhaisemman prioriteetin arvon omaavalle elementille annetaan korkeampi prioriteetti prioriteettiluettelossa. Jos meillä on esimerkiksi seuraavat elementit prioriteettijonossa, jotka on järjestetty nousevaan järjestykseen, kuten 4,6,8,9,10. Tässä 4 on pienin luku, joten se saa korkeimman prioriteetin prioriteettijonossa, joten kun poistamme jonosta tämäntyyppisestä prioriteettijonosta, 4 poistaa jonosta ja jonosta palautuu 4.

2) Laskevassa järjestyksessä Priority Queue

Kuten ehkä tiedät, juurisolmu on maksimielementti max-keossa. Se myös poistaa ensimmäisenä elementin, jolla on korkein prioriteetti. Tämän seurauksena juurisolmu poistetaan jonosta. Tämä poisto jättää tyhjän tilan, joka täytetään tulevaisuudessa uusilla lisäyksillä. Keon invarianttia ylläpidetään sitten vertaamalla äskettäin lisättyä elementtiä kaikkiin muihin jonon merkintöihin.

Prioriteettijonojen tyypit

Ero prioriteettijonon ja normaalin jonon välillä?

Jonossa oleville elementeille ei ole liitetty prioriteettia, vaan FIFO (first-in-first-out) -sääntö on toteutettu, kun taas prioriteettijonossa elementeillä on prioriteetti. Elementit, joilla on korkeampi prioriteetti, tarjotaan ensin.

Kuinka ottaa prioriteettijono käyttöön?

Prioriteettijono voidaan toteuttaa käyttämällä seuraavia tietorakenteita:

• Taulukot
• Linkitetty lista
• Keon tietorakenne
• Binäärihakupuu

Keskustellaan näistä kaikista yksityiskohtaisesti.

1) Toteuta prioriteettijono taulukon avulla:

Yksinkertainen toteutus on käyttää seuraavan rakenteen matriisia.

struct item {
int erä;
int prioriteetti;
}

enqueue(): Tätä funktiota käytetään lisäämään uusia tietoja jonoon. dequeue(): Tämä funktio poistaa korkeimman prioriteetin omaavan elementin jonosta. peek()/top(): Tätä funktiota käytetään saamaan jonon korkeimman prioriteetin elementti poistamatta sitä jonosta.

C++

>

>

Java

>

>

Python 3

>

>

C#

java-piste

>

>

Javascript

>

>

16 14 12>

Huomautus: Lukea Tämä artikkeli Lisätietoja.

2) Ota prioriteettijono käyttöön linkitetyn luettelon avulla:

LinkedList-toteutuksessa merkinnät lajitellaan laskevaan järjestykseen niiden prioriteetin perusteella. Korkeimman prioriteetin elementti lisätään aina prioriteettijonon etupuolelle, joka muodostetaan linkitettyjen listojen avulla. Toiminnot kuten työntää() , pop() , ja kurkistaa() käytetään prioriteettijonon toteuttamiseen linkitetyn luettelon avulla, ja ne selitetään seuraavasti:

push(): Tätä toimintoa käytetään lisäämään uusia tietoja jonoon. pop(): Tämä toiminto poistaa korkeimman prioriteetin omaavan elementin jonosta. peek() / top(): Tätä funktiota käytetään saamaan jonon korkeimman prioriteetin elementti poistamatta sitä jonosta.

C++

b- ja b-puu

>

>

Java

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python3 code to implement Priority Queue> # using Singly Linked List> # Class to create new node which includes> # Node Data, and Node Priority> class> PriorityQueueNode:> >def> _init_(>self>, value, pr):> >self>.data>=> value> >self>.priority>=> pr> >self>.>next> => None> # Implementation of Priority Queue> class> PriorityQueue:> >def> _init_(>self>):> >self>.front>=> None> ># Method to check Priority Queue is Empty> ># or not if Empty then it will return True> ># Otherwise False> >def> isEmpty(>self>):> >return> True> if> self>.front>=>=> None> else> False> ># Method to add items in Priority Queue> ># According to their priority value> >def> push(>self>, value, priority):> ># Condition check for checking Priority> ># Queue is empty or not> >if> self>.isEmpty()>=>=> True>:> ># Creating a new node and assigning> ># it to class variable> >self>.front>=> PriorityQueueNode(value,> >priority)> ># Returning 1 for successful execution> >return> 1> >else>:> ># Special condition check to see that> ># first node priority value> >if> self>.front.priority   # Creating a new node  newNode = PriorityQueueNode(value,  priority)  # Updating the new node next value  newNode.next = self.front  # Assigning it to self.front  self.front = newNode  # Returning 1 for successful execution  return 1  else:  # Traversing through Queue until it  # finds the next smaller priority node  temp = self.front  while temp.next:  # If same priority node found then current  # node will come after previous node  if priority>= temp.next.priority: break temp = temp.next newNode = PriorityQueueSolmu(arvo, prioriteetti) newNode.next = temp.next temp.next = uusiSolmu # Palauttaa 1 onnistuneelle suoritukselle return 1 # Menetelmä korkean prioriteetin kohteen # poistamiseksi Priority Queue def pop(self): # Tarkistuksen ehto # Priority Queue on tyhjä vai ei, jos self.isEmpty() == True: return else: # Poistetaan korkean prioriteetin solmu # Priority Queue -jonosta ja päivitetään edessä # seuraavalla solmu self.front = self.front.next return 1 # Menetelmä korkean prioriteetin solmun palauttamiseksi # arvo Ei poisteta sitä def peek(self): # Ehdon tarkistus tarkistukseen Priority # Jono on tyhjä tai ei, jos self.isEmpty() == True: return else: return self.front.data # Menetelmä kulkea prioriteetin läpi # Jono def traverse(self): # Tarkistuksen ehto Prioriteetti # Jono on tyhjä tai ei, jos self.isEmpty() == True: return ' Jono on tyhjä!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Ohjainkoodi if _name_ == '_main_': # Luodaan Priority # Queuen esiintymä ja arvojen lisääminen # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Kulkeminen prioriteettijonon läpi pq.traverse() # Korkeimman prioriteetin kohteen # poistaminen prioriteettijonosta pq.pop()>
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# code to implement Priority Queue> // using Linked List> using> System;> class> GFG> {> >// Node> >public> class> Node> >{> >public> int> data;> >// Lower values indicate> >// higher priority> >public> int> priority;> >public> Node next;> >}> >public> static> Node node =>new> Node();> >// Function to Create A New Node> >public> static> Node newNode(>int> d,>int> p)> >{> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> >}> >// Return the value at head> >public> static> int> peek(Node head)> >{> >return> (head).data;> >}> >// Removes the element with the> >// highest priority from the list> >public> static> Node pop(Node head)> >{> >Node temp = head;> >(head) = (head).next;> >return> head;> >}> >// Function to push according to priority> >public> static> Node push(Node head,> >int> d,>int> p)> >{> >Node start = (head);> >// Create new Node> >Node temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> ((head).priority   {   // Insert New Node before head   temp.next = head;   (head) = temp;   }   else  {   // Traverse the list and find a   // position to insert new node   while (start.next != null &&   start.next.priority>p) { aloitus = aloitus.seuraava;   } // Joko luettelon lopussa // tai vaaditussa paikassa temp.next = start.next;   start.next = lämpötila;   } paluupää;   } // Toiminto tarkistaa onko lista tyhjä public static int isEmpty(Solmupää) { return ((head) == null) ? 1:0;   } // Ohjainkoodi public static void Main(string[] args) { // Luo prioriteettijono // 7.4.5.6 Node pq = newNode(4, 1);   pq = push(pq, 5, 2);   pq = push(pq, 6, 3);   pq = push(pq, 7, 0);   while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq));   pq = pop(pq);   } } } // Tämän koodin on toimittanut ishankhandelwals.>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
nimeä Linuxin hakemisto uudelleen
 
 
 
 
 
 // JavaScript code to implement Priority Queue> // using Linked List> // Node> class Node {> >// Lower values indicate> >// higher priority> >constructor() {> >this>.data = 0;> >this>.priority = 0;> >this>.next =>null>;> >}> }> var> node =>new> Node();> // Function to Create A New Node> function> newNode(d, p) {> >var> temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> }> // Return the value at head> function> peek(head) {> >return> head.data;> }> // Removes the element with the> // highest priority from the list> function> pop(head) {> >var> temp = head;> >head = head.next;> >return> head;> }> // Function to push according to priority> function> push(head, d, p) {> >var> start = head;> >// Create new Node> >var> temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> (head.priority   // Insert New Node before head  temp.next = head;  head = temp;  }  else {  // Traverse the list and find a  // position to insert new node  while (start.next != null && start.next.priority>p) { aloitus = aloitus.seuraava;  } // Joko luettelon lopussa // tai vaaditussa paikassa temp.next = start.next;  start.next = lämpötila;  } paluupää; } // Tarkistettava toiminto on tyhjä funktio isEmpty(head) { return head == null ? 1:0; } // Ohjainkoodi // Luo prioriteettijono // 7.4.5.6 var pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' ');  pq = pop(pq); } // Tämän koodin tarjoaa ishankhandelwals.>>
 
 
 
 
    
 
> 
    
  6 5 4 7>
 
Katso lisätietoja tästä artikkelista.
  
 
  Huomautus: Voimme myös käyttää linkitettyä listaa, kaikkien linkitettyjen listojen toimintojen aika monimutkaisuus pysyy samana kuin array. Linkitetyn luettelon etu on   deleteHighestPriority()   voi olla tehokkaampaa, koska meidän ei tarvitse siirtää kohteita.
 
 
  3) Toteuta prioriteettijono kasojen avulla:  
 
Binaarikeko on yleensä suositeltava prioriteettijonojen toteutuksessa, koska kasat tarjoavat paremman suorituskyvyn kuin taulukot tai LinkedList. Ottaen huomioon kasan ominaisuudet suurimman avaimen merkintä on päällä ja voidaan poistaa välittömästi. Kestää kuitenkin aikaa O(log n) palauttaa jäljellä olevien avainten pino-ominaisuus. Jos toinen merkintä on kuitenkin lisättävä välittömästi, osa tästä ajasta voidaan yhdistää O(log n) -aikaan, joka tarvitaan uuden merkinnän lisäämiseen. Siten prioriteettijonon esittäminen kasona osoittautuu edulliseksi suurelle n:lle, koska se esitetään tehokkaasti viereisessä muistissa ja vaatii taatusti vain logaritmisen ajan sekä lisäyksiin että poistoihin. Binaarikeon toiminnot ovat seuraavat:
 
insert(p): Lisää uuden elementin prioriteetilla p. extractMax(): Purkaa elementin, jolla on suurin prioriteetti. poista(i): Poistaa iteraattorin i osoittaman elementin. getMax(): Palauttaa elementin, jolla on suurin prioriteetti. changePriority(i, p): Muuttaa osoittaman elementin prioriteettia minä p .
 
 
 
 
Binäärikasa
 
 
 
insert()
 
 
 
Poista()
 
 
 
kurkistaa()
 
 
 
 
 
 
Aika monimutkaisuus
 
 
 
O(log n)
 
 
 
O(log n)
 
 
 
O(1)
 
 
 
 
  
 
Katso tästä artikkelista koodin käyttöönotto.
 
 
  4) Ota prioriteettijono käyttöön binaarihakupuulla:  
 
Itsetasapainottavaa binaarihakupuuta, kuten AVL-puuta, punamustapuuta jne., voidaan myös käyttää prioriteettijonon toteuttamiseen. Toiminnot, kuten peek(), insert() ja delete(), voidaan suorittaa käyttämällä BST:tä.
 
 
 
Binäärihakupuu
 
kurkistaa()
 
insert()
 
poistaa()
 
 
 
 
Aika monimutkaisuus
 
O(1)
 
O(log n)
 
O(log n)
 
 
 
 
  Priority Queuen sovellukset:  
 
 
Prosessorin ajoitus
 
Graafialgoritmit, kuten Dijkstran lyhimmän polun algoritmi, Primin minimivirityspuu jne.
 
Pinon toteutus
 
Kaikki prioriteettijonon sovellukset
 
  Priority Queue C++:ssa  
 
Priority Queue Javassa
 
  Priority Queue Pythonissa  
 
Priority Queue JavaScriptissä
 
Viimeisimmät artikkelit Priority Queuesta!