A cua de prioritats és un tipus de cua que ordena els elements en funció dels seus valors de prioritat. Els elements amb valors de prioritat més alts normalment es recuperen abans que els elements amb valors de prioritat més baixa.

En una cua de prioritats, cada element té un valor de prioritat associat. Quan afegiu un element a la cua, s'insereix en una posició en funció del seu valor de prioritat. Per exemple, si afegiu un element amb un valor de prioritat alta a una cua de prioritat, es pot inserir prop de la part davantera de la cua, mentre que un element amb un valor de prioritat baixa es pot inserir a la part posterior.

Hi ha diverses maneres d'implementar una cua de prioritats, com ara l'ús d'una matriu, una llista enllaçada, un munt o un arbre de cerca binari. Cada mètode té els seus propis avantatges i desavantatges, i la millor opció dependrà de les necessitats específiques de la vostra aplicació.

Les cues de prioritat s'utilitzen sovint en sistemes en temps real, on l'ordre en què es processen els elements pot tenir conseqüències importants. També s'utilitzen en algorismes per millorar les seves eficiències, com ara algorisme de Dijkstra per trobar el camí més curt en un gràfic i l'algoritme de cerca A* per trobar el camí.

Propietats de la cua de prioritats

Per tant, una cua de prioritat és una extensió de la cua amb les següents propietats.

• Cada element té una prioritat associada.
• Un element amb prioritat alta es retira de la cua abans d'un element amb prioritat baixa.
• Si dos elements tenen la mateixa prioritat, es serveixen segons el seu ordre a la cua.

A la cua de prioritat següent, un element amb un valor ASCII màxim tindrà la prioritat més alta. Els elements amb prioritat més alta se serveixen primer.

Com s'assigna la prioritat als elements d'una cua de prioritats?

En una cua de prioritats, generalment, es considera el valor d'un element per assignar la prioritat.

Per exemple, l'element amb el valor més alt s'assigna la prioritat més alta i l'element amb el valor més baix s'assigna la prioritat més baixa. També es pot utilitzar el cas invers, és a dir, es pot assignar la prioritat més alta a l'element amb el valor més baix. A més, es pot assignar la prioritat segons les nostres necessitats.

Operacions d'una cua de prioritat:

Una cua de prioritat típica admet les operacions següents:

1) Inserció en una cua de prioritat

Quan s'insereix un element nou en una cua de prioritat, es mou a la ranura buida de dalt a baix i d'esquerra a dreta. Tanmateix, si l'element no es troba al lloc correcte, es compararà amb el node pare. Si l'element no està en l'ordre correcte, els elements s'intercanvien. El procés d'intercanvi continua fins que tots els elements es col·loquen a la posició correcta.

2) Supressió en una cua de prioritat

Com sabeu que en un munt màxim, l'element màxim és el node arrel. I eliminarà primer l'element que tingui la màxima prioritat. Així, elimineu el node arrel de la cua. Aquesta eliminació crea una ranura buida, que s'omplirà encara més amb una nova inserció. A continuació, compara l'element nou inserit amb tots els elements dins de la cua per mantenir l'invariant de la pila.

3) Mirar en una cua de prioritat

Aquesta operació ajuda a retornar l'element màxim de Max Heap o l'element mínim de Min Heap sense eliminar el node de la cua de prioritats.

Tipus de cua de prioritats:

1) Cua de prioritat d'ordre ascendent

Com el seu nom indica, en la cua de prioritats d'ordre ascendent, l'element amb un valor de prioritat més baix té una prioritat més alta a la llista de prioritats. Per exemple, si tenim els següents elements en una cua de prioritats disposats en ordre ascendent com 4,6,8,9,10. Aquí, 4 és el nombre més petit, per tant, obtindrà la prioritat més alta en una cua de prioritat i, per tant, quan sortim de la cua d'aquest tipus de cua de prioritat, 4 eliminarà de la cua i la cua retornarà 4.

2) Cua de prioritat d'ordre descendent

El node arrel és l'element màxim d'un munt màxim, com ja sabeu. També eliminarà primer l'element amb la prioritat més alta. Com a resultat, el node arrel s'elimina de la cua. Aquesta supressió deixa un espai buit, que s'omplirà amb noves insercions en el futur. Aleshores, l'invariant de la pila es manté comparant l'element nou inserit amb totes les altres entrades de la cua.

Tipus de cues de prioritat

Diferència entre la cua de prioritat i la cua normal?

No s'adjunta cap prioritat als elements d'una cua, s'implementa la regla del primer en entrar, primer en sortir (FIFO), mentre que, en una cua de prioritat, els elements tenen prioritat. Els elements amb prioritat més alta se serveixen primer.

Com implementar la cua de prioritats?

La cua de prioritats es pot implementar mitjançant les estructures de dades següents:

• Arrays
• Llista enllaçada
• Estructura de dades heap
• Arbre de cerca binari

Parlem de tot això en detall.

1) Implementeu la cua de prioritats mitjançant la matriu:

Una implementació senzilla és utilitzar una matriu de l'estructura següent.

element d'estructura {
int element;
int prioritat;
}

enqueue(): Aquesta funció s'utilitza per inserir dades noves a la cua. dequeue(): Aquesta funció elimina l'element amb la prioritat més alta de la cua. peek()/top(): aquesta funció s'utilitza per obtenir l'element de màxima prioritat a la cua sense eliminar-lo de la cua.

C++

comparació de cadenes java

>

>

Java

>

>

Python 3

>

>

C#

>

1 a 100 roman núm

>

Javascript

>

>

16 14 12>

Nota: Llegeix Aquest article per a més detalls.

2) Implementeu la cua de prioritats mitjançant una llista enllaçada:

En una implementació de LinkedList, les entrades s'ordenen en ordre descendent en funció de la seva prioritat. L'element de màxima prioritat sempre s'afegeix al capdavant de la cua de prioritat, que es forma mitjançant llistes enllaçades. Les funcions com empènyer () , pop() , i ullada() s'utilitzen per implementar una cua de prioritats mitjançant una llista enllaçada i s'expliquen de la següent manera:

push(): Aquesta funció s'utilitza per inserir dades noves a la cua. pop(): Aquesta funció elimina l'element amb la prioritat més alta de la cua. peek() / top(): aquesta funció s'utilitza per obtenir l'element de màxima prioritat a la cua sense eliminar-lo de la cua.

C++

actualització des de join sql

>

>

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 (valor, prioritat) newNode.next = temp.next temp.next = newNode # Tornant 1 per a una execució correcta retornar 1 # Mètode per eliminar l'element d'alta prioritat # de the Priority Queue def pop(self): # Comprovació de la condició per comprovar # Priority Queue està buida o no si self.isEmpty() == True: return else: # Eliminació del node d'alta prioritat de # Priority Queue, i actualització del front # amb el següent node self.front = self.front.next return 1 # Mètode per retornar node d'alta prioritat # valor No s'elimina def peek(self): # Comprovació de condicions per comprovar Prioritat # La cua està buida o no si self.isEmpty() == True: return else: return self.front.data # Mètode per recórrer la prioritat # Queue def traverse(self): # Comprovació de condicions per comprovar Prioritat # La cua està buida o no si self.isEmpty() == Veritable: retorna ' La cua està buida!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Codi del controlador if _name_ == '_main_': # Creació d'un instància de Priority # Queue, i afegint valors # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Recorregut per la cua de prioritat pq.traverse() # S'està eliminant l'element de prioritat més alta # per a la cua de prioritat 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) { inici = inici.següent;   } // Ja sigui al final de la llista // o a la posició requerida temp.next = start.next;   start.next = temp;   } retorn cap;   } // La funció a comprovar és la llista està buida public static int isEmpty(Node head) { return ((head) == null)? 1: 0;   } // Codi del controlador public static void Main(string[] args) { // Crea una cua de prioritats // 7.4.5.6 Node pq = newNode(4, 1);   pq = push(pq, 5, 2);   pq = push(pq, 6, 3);   pq = push(pq, 7, 0);   mentre que (és buit(pq) == 0) { Console.Write('{0:D} ', peek(pq));   pq = pop(pq);   } } } // Aquest codi és aportat per ishankhandelwals.>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
python rstrip
 
 
 
 
 
 // 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) { inici = inici.següent;  } // Ja sigui al final de la llista // o a la posició requerida temp.next = start.next;  start.next = temp;  } retorn cap; } // La funció a comprovar és la llista està buida la funció és buida (capçalera) { cap de retorn == null? 1: 0; } // Codi del controlador // Crea una cua de prioritats // 7.4.5.6 var pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); mentre que (és buit(pq) == 0) { console.log(peek(pq),' ');  pq = pop(pq); } // Aquest codi és aportat per ishankhandelwals.>>>
 
 
 
 
    
 
> 
    
  6 5 4 7>
 
Consulteu aquest article per obtenir més detalls.
  
 
  Nota: També podem utilitzar la llista enllaçada, la complexitat temporal de totes les operacions amb llista enllaçada segueix sent la mateixa que la matriu. L'avantatge amb la llista enllaçada és   deleteHighestPriority()   pot ser més eficient ja que no hem de moure elements.
 
 
  3) Implementeu la cua de prioritats mitjançant munts:  
 
En general, es prefereix Binary Heap per a la implementació de la cua de prioritat perquè els munts ofereixen un millor rendiment en comparació amb les matrius o LinkedList. Tenint en compte les propietats d'un munt, l'entrada amb la clau més gran es troba a la part superior i es pot eliminar immediatament. Tanmateix, es necessitarà un temps O(log n) per restaurar la propietat de l'emmagatzematge dinàmic de les claus restants. Tanmateix, si s'ha d'inserir una altra entrada immediatament, una part d'aquest temps es pot combinar amb el temps O(log n) necessari per inserir la nova entrada. Així, la representació d'una cua de prioritat com un munt resulta avantatjosa per a n gran, ja que es representa de manera eficient en l'emmagatzematge contigu i es garanteix que només requereix temps logarítmic tant per a les insercions com per a les supressions. Les operacions amb Binary Heap són les següents:
 
insert(p): Insereix un element nou amb prioritat p. extractMax(): extreu un element amb la màxima prioritat. remove(i): elimina un element apuntat per un iterador i. getMax(): retorna un element amb la màxima prioritat. changePriority(i, p): Canvia la prioritat d'un element assenyalat per i a la pàg .
 
 
 
 
Munt binari
 
 
 
inserir ()
 
 
 
eliminar ()
 
 
 
ullada()
 
 
 
 
 
 
Complexitat temporal
 
 
 
O(log n)
 
 
 
O(log n)
 
 
 
O(1)
 
 
 
 
  
 
Consulteu aquest article per a la implementació del codi.
 
 
  4) Implementeu la cua de prioritats mitjançant l'arbre de cerca binari:  
 
També es pot utilitzar un arbre de cerca binari d'autoequilibri com l'arbre AVL, l'arbre vermell-negre, etc. per implementar una cua de prioritat. Operacions com peek(), insert() i delete() es poden realitzar mitjançant BST.
 
 
 
Arbre de cerca binari
 
ullada()
 
inserir ()
 
suprimir()
 
 
 
 
Complexitat temporal
 
O(1)
 
O(log n)
 
O(log n)
 
 
 
 
  Aplicacions de la cua de prioritats:  
 
 
Programació de la CPU
 
Algorismes gràfics com l'algoritme del camí més curt de Dijkstra, l'arbre d'abast mínim de Prim, etc.
 
Implementació de la pila
 
Totes les aplicacions de la cua de prioritats
 
  Cua de prioritats en C++  
 
Cua de prioritats a Java
 
  Cua de prioritats en Python  
 
Cua de prioritats en JavaScript
 
Articles recents sobre Priority Queue!