A coada de prioritate este un tip de coadă care aranjează elementele pe baza valorilor lor de prioritate. Elementele cu valori de prioritate mai mare sunt de obicei preluate înaintea elementelor cu valori de prioritate mai mică.

Într-o coadă de prioritate, fiecare element are asociată o valoare de prioritate. Când adăugați un element în coadă, acesta este inserat într-o poziție bazată pe valoarea sa de prioritate. De exemplu, dacă adăugați un element cu o valoare de prioritate ridicată la o coadă de prioritate, acesta poate fi inserat lângă partea din față a cozii, în timp ce un element cu o valoare de prioritate scăzută poate fi inserat în partea din spate.

Există mai multe moduri de a implementa o coadă de prioritate, inclusiv utilizarea unei matrice, a unei liste conectate, a unui heap sau a unui arbore de căutare binar. Fiecare metodă are propriile avantaje și dezavantaje, iar cea mai bună alegere va depinde de nevoile specifice ale aplicației dumneavoastră.

Cozile prioritare sunt adesea folosite în sistemele în timp real, unde ordinea în care sunt procesate elementele poate avea consecințe semnificative. De asemenea, sunt utilizați în algoritmi pentru a-și îmbunătăți eficiența, cum ar fi algoritmul lui Dijkstra pentru găsirea celei mai scurte căi într-un grafic și algoritmul de căutare A* pentru găsirea căii.

Proprietățile Cozii de prioritate

Deci, o coadă prioritară este o extensie a coadă cu următoarele proprietăți.

• Fiecare articol are o prioritate asociată.
• Un element cu prioritate mare este scos din coadă înaintea unui element cu prioritate scăzută.
• Dacă două elemente au aceeași prioritate, acestea sunt servite în funcție de ordinea lor în coadă.

În coada de prioritate de mai jos, un element cu o valoare ASCII maximă va avea cea mai mare prioritate. Elementele cu prioritate mai mare sunt servite mai întâi.

Cum se atribuie prioritate elementelor dintr-o coadă de prioritate?

Într-o coadă de prioritate, în general, valoarea unui element este luată în considerare pentru atribuirea priorității.

De exemplu, elementului cu cea mai mare valoare i se atribuie cea mai mare prioritate, iar elementului cu cea mai mică valoare i se atribuie cea mai mică prioritate. Se poate folosi și cazul invers, adică elementului cu cea mai mică valoare i se poate atribui cea mai mare prioritate. De asemenea, prioritatea poate fi atribuită în funcție de nevoile noastre.

Operațiuni ale unei cozi prioritare:

O coadă de prioritate tipică acceptă următoarele operații:

1) Inserarea într-o coadă prioritară

Când un nou element este inserat într-o coadă de prioritate, acesta se deplasează în slotul gol de sus în jos și de la stânga la dreapta. Cu toate acestea, dacă elementul nu este în locul corect, atunci va fi comparat cu nodul părinte. Dacă elementul nu este în ordinea corectă, elementele sunt schimbate. Procesul de schimbare continuă până când toate elementele sunt plasate în poziția corectă.

2) Ștergerea într-o coadă prioritară

După cum știți că într-un heap maxim, elementul maxim este nodul rădăcină. Și va elimina primul element care are prioritate maximă. Astfel, eliminați nodul rădăcină din coadă. Această eliminare creează un slot gol, care va fi umplut în continuare cu o nouă inserare. Apoi, compară elementul nou introdus cu toate elementele din coadă pentru a menține invarianta heap.

3) Priviți într-o coadă prioritară

Această operațiune ajută la returnarea elementului maxim din Max Heap sau a elementului minim din Min Heap fără a șterge nodul din coada de prioritate.

Tipuri de coadă prioritară:

1) Coada de prioritate pentru ordine crescătoare

După cum sugerează și numele, în coada de priorități în ordine crescătoare, elementului cu o valoare de prioritate mai mică i se acordă o prioritate mai mare în lista de priorități. De exemplu, dacă avem următoarele elemente într-o coadă de prioritate aranjate în ordine crescătoare precum 4,6,8,9,10. Aici, 4 este cel mai mic număr, prin urmare, va primi cea mai mare prioritate într-o coadă de prioritate și astfel, atunci când scoatem coada din acest tip de coadă de prioritate, 4 va elimina din coadă și scoaterea din coadă va returna 4.

2) Coadă de prioritate în ordine descendentă

Nodul rădăcină este elementul maxim într-un heap maxim, după cum probabil știți. De asemenea, va elimina mai întâi elementul cu cea mai mare prioritate. Ca rezultat, nodul rădăcină este eliminat din coadă. Această ștergere lasă un spațiu gol, care va fi umplut cu inserții noi în viitor. Invariantul heap este apoi menținut prin compararea elementului nou introdus cu toate celelalte intrări din coadă.

Tipuri de cozi prioritare

Diferența dintre coada prioritară și coada normală?

Nu există o prioritate atașată elementelor dintr-o coadă, este implementată regula primul-intrat-primul-ieșit (FIFO), în timp ce, într-o coadă de prioritate, elementele au prioritate. Elementele cu prioritate mai mare sunt servite mai întâi.

carcasa comutatorului java

Cum se implementează Coada prioritară?

Coada de prioritate poate fi implementată folosind următoarele structuri de date:

• Matrice
• Lista legată
• Structura de date heap
• Arborele de căutare binar

Să discutăm toate acestea în detaliu.

1) Implementați cozile prioritare folosind matrice:

O implementare simplă este utilizarea unui tablou cu următoarea structură.

struct item {
int element;
int prioritate;
}

enqueue(): Această funcție este folosită pentru a introduce date noi în coadă. dequeue(): Această funcție elimină elementul cu cea mai mare prioritate din coadă. peek()/top(): Această funcție este folosită pentru a obține elementul cu cea mai mare prioritate din coadă fără a-l elimina din coadă.

C++

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

16 14 12>

Notă: Citit Acest articol pentru mai multe detalii.

2) Implementați coada de prioritate folosind lista legată:

Într-o implementare LinkedList, intrările sunt sortate în ordine descrescătoare în funcție de prioritatea lor. Elementul cu cea mai mare prioritate este întotdeauna adăugat în partea din față a cozii de prioritate, care este formată folosind liste legate. Funcțiile ca Apăsaţi() , pop() , și arunca o privire() sunt folosite pentru a implementa o coadă de prioritate folosind o listă legată și sunt explicate după cum urmează:

push(): Această funcție este folosită pentru a introduce date noi în coadă. pop(): Această funcție elimină elementul cu cea mai mare prioritate din coadă. peek() / top(): Această funcție este folosită pentru a obține elementul cu cea mai mare prioritate din coadă fără a-l elimina din coadă.

C++

>

>

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 = PriorityQueueNode(valoare, prioritate) newNode.next = temp.next temp.next = newNode # Returnarea 1 pentru execuție cu succes return 1 # Metoda de eliminare a elementului cu prioritate ridicată # din the Priority Queue def pop(self): # Verificarea condiției pentru verificare # Priority Queue este goală sau nu dacă self.isEmpty() == True: return else: # Eliminarea nodului cu prioritate ridicată din # Priority Queue și actualizarea frontului # cu următorul node self.front = self.front.next return 1 # Metoda de returnare a nodului cu prioritate mare # valoare Nu o elimina def peek(self): # Verificare conditie pentru verificarea Prioritate # Coada este goala sau nu daca self.isEmpty() == True: return else: return self.front.data # Metoda de parcurs prin Prioritate # Queue def traverse(self): # Verificare condiție pentru verificarea Prioritate # Coada este goală sau nu dacă self.isEmpty() == Adevărat: returnează ' Coada este goală!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Cod driver if _name_ == '_main_': # Crearea unui instanță de Priority # Queue și adăugarea valorilor # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Traversarea prin coada de prioritate pq.traverse() # Eliminarea elementului cu cea mai mare prioritate # pentru coada de prioritate 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) { start = start.next;   } // Fie la sfârșitul listei // fie la poziția dorită temp.next = start.next;   start.next = temp;   } cap înapoi;   } // Funcția de verificat este lista este goală public static int isEmpty(Node head) { return ((head) == null) ? 1: 0;   } // Cod driver public static void Main(string[] args) { // Creați o coadă de prioritate // 7.4.5.6 Nodul 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);   } } } // Acest cod este contribuit de ishankhandelwals.>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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) { start = start.next;  } // Fie la sfârșitul listei // fie la poziția dorită temp.next = start.next;  start.next = temp;  } cap înapoi; } // Funcția de verificat este lista este goală funcția isEmpty(head) { return head == null ? 1: 0; } // Cod driver // Creați o coadă de prioritate // 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); } // Acest cod este contribuit de ishankhandelwals.>>>
 
 
 
 
    
 
> 
    
  6 5 4 7>
 
Consultați acest articol pentru mai multe detalii.
  
 
  Notă: De asemenea, putem folosi Linked List, complexitatea de timp a tuturor operațiunilor cu lista legată rămâne aceeași ca și matricea. Avantajul cu lista legată este   deleteHighestPriority()   poate fi mai eficient, deoarece nu trebuie să mutăm elemente.
 
 
  3) Implementați coada prioritară folosind grămezi:  
 
Heap-ul binar este în general preferat pentru implementarea cozii prioritare, deoarece heap-urile oferă performanțe mai bune în comparație cu matricele sau LinkedList. Având în vedere proprietățile unui morman, intrarea cu cea mai mare cheie se află în partea de sus și poate fi eliminată imediat. Cu toate acestea, va dura timp O(log n) pentru a restabili proprietatea heap pentru cheile rămase. Cu toate acestea, dacă o altă intrare urmează să fie inserată imediat, atunci o parte din acest timp poate fi combinată cu timpul O(log n) necesar pentru a introduce noua intrare. Astfel, reprezentarea unei cozi de prioritate ca un heap se dovedește avantajoasă pentru n mare, deoarece este reprezentată eficient în stocarea contiguă și este garantat să necesite doar timp logaritmic atât pentru inserții, cât și pentru ștergere. Operațiunile pe heap binar sunt după cum urmează:
 
insert(p): Inserează un element nou cu prioritate p. extractMax(): Extrage un element cu prioritate maximă. remove(i): elimină un element indicat de un iterator i. getMax(): Returnează un element cu prioritate maximă. changePriority(i, p): modifică prioritatea unui element indicat de i la p .
 
 
 
 
Heap binar
 
 
 
introduce()
 
 
 
elimina()
 
 
 
arunca o privire()
 
 
 
 
 
 
Complexitatea timpului
hopa concepte în java
 
 
 
O(log n)
 
 
 
O(log n)
 
 
 
O(1)
 
 
 
 
  
 
Consultați acest articol pentru implementarea codului.
 
 
  4) Implementați coada de prioritate folosind arborele de căutare binar:  
 
Un arbore de căutare binar cu auto-echilibrare, cum ar fi arborele AVL, arborele roșu-negru, etc. poate fi, de asemenea, utilizat pentru a implementa o coadă de prioritate. Operațiuni precum peek(), insert() și delete() pot fi efectuate folosind BST.
 
 
 
Arborele de căutare binar
 
arunca o privire()
 
introduce()
 
șterge()
 
 
 
 
Complexitatea timpului
 
O(1)
 
O(log n)
 
O(log n)
 
 
 
 
  Aplicații ale Cozii prioritare:  
 
 
Programarea CPU
 
Algoritmi grafici precum algoritmul cu calea cea mai scurtă a lui Dijkstra, arborele de întindere minim al lui Prim etc.
 
Implementarea stivei
 
Toate aplicațiile Cozii de prioritate
 
  Coada prioritară în C++  
 
Coada prioritară în Java
 
  Coada prioritară în Python  
 
Coada prioritară în JavaScript
 
Articole recente despre Priority Queue!