Menú

Estructura de dades de la cua de prioritat en C ++ amb il·lustració

  • Principal
  • Altres
  • Estructura de dades de la cua de prioritat en C ++ amb il·lustració

priority queue data structure c with illustration

Proveu El Nostre Instrument Per Eliminar Problemes

Introducció a la cua de prioritat en C ++ amb il·lustració.

Priority Queue és una extensió de la cua que hem comentat al nostre últim tutorial.

És similar a la cua en certs aspectes i, tanmateix, difereix de la cua ordinària en els punts següents:

  • Cada element de la cua de prioritats està associat a una prioritat.
  • L'element amb la màxima prioritat és el primer element que es treu de la cua.
  • Si més d'un element té la mateixa prioritat, es considera el seu ordre a la cua.

=> Feu clic aquí per obtenir la sèrie de formació Absolute C ++.

Cua de prioritat a C ++

Podem visualitzar la cua de prioritat com una versió modificada de la cua, tret que quan l’element es tregui de la cua, primer es recuperarà l’element amb la màxima prioritat. Per tant, preferim utilitzar les cues de prioritat en lloc de les cues quan necessitem processar els elements en funció de la prioritat.

Què aprendreu:

Operacions bàsiques

Analitzem algunes de les operacions bàsiques admeses per la cua de prioritats.

  • Insereix (element, prioritat): Insereix un element a la cua de prioritats amb una prioritat determinada.
  • getHighestPriority (): Retorna un element amb la màxima prioritat.
  • deleteHighestPriority (): Elimina un element amb la màxima prioritat.

A part de les operacions anteriors, també podem utilitzar les operacions de cua normals com isEmpty (), isFull () i peek ().

Il·lustració

Vegem una il·lustració de la cua de prioritat. A efectes de simplicitat, utilitzarem caràcters ASCII com a elements a la cua de prioritat. Com més alt sigui el valor ASCII, més alta serà la prioritat.

Estat inicial: cua de prioritat (PQ) - {} => buida

il·lustració de la cua de prioritat

A la il·lustració anterior, veiem que l'operació d'inserció és similar a una cua normal. Però quan anomenem 'deleteHighestPriority' per a la cua de prioritat, l'element amb la màxima prioritat s'elimina primer.

Per tant, la primera vegada que anomenem aquesta funció, l'element O s'elimina, mentre que la segona vegada, l'element M s'elimina, ja que té una prioritat superior a G i A.

Implementació de cues de prioritat a C ++

Les cues de prioritat es poden implementar mitjançant:

# 1) Matrius / llistes enllaçades

Podem implementar les cues de prioritat mitjançant matrius i aquesta és la implementació més senzilla per a les cues de prioritat.

Per representar els elements de la cua de prioritat, només podem declarar una estructura de la manera següent:

struct pq_item{ int item; int priority; };

També hem declarat la prioritat de cada element.

Per inserir un element nou a la cua de prioritat, simplement hem d'inserir l'element al final de la matriu.

Per obtenir l'element de la cua mitjançant getHighestPriority (), hem de recórrer la matriu des del principi i retornar l'element amb la màxima prioritat.

De la mateixa manera, per eliminar l’element de la cua mitjançant l’operació deleteHighestPriority, hem de recórrer tota la matriu i eliminar l’element amb la màxima prioritat. A continuació, moveu tots els altres elements després de l'element suprimit, una posició cap enrere.

També podem implementar la cua de prioritat mitjançant una llista enllaçada. Podem realitzar totes les operacions de manera similar a les matrius. L'única diferència és que no hem de moure els elements després de trucar a deleteHighestPriority.

# 2) Muntatges

Utilitzar munts per implementar una cua de prioritat és la manera més eficient i proporciona un rendiment molt millor en comparació amb les llistes i matrius enllaçats. Al contrari de la llista i la matriu enllaçades, la implementació de l'emmagatzematge dinàmic requereix temps O (logn) per a les operacions d'inserció i eliminació de la cua de prioritat. Feu funcionar, getHighestPriority triga O (1) temps.

# 3) Cua de prioritat integrada a la biblioteca de plantilles estàndard (STL) a C ++

A C ++, tenim una cua prioritària com a classe adaptativa de contenidors, dissenyada de manera que l’element més alt sigui el primer element de la cua i tots els elements estiguin en ordre decreixent.

Per tant, cada element de la cua de prioritats té una prioritat fixa.

Tenim classe en STL, que conté la implementació de la cua prioritària.

Les diverses operacions admeses per la cua de prioritat són les següents:

  1. prioritat_cua :: mida (): Retorna la mida de la cua.
  2. prioritat_cua :: buit (): Comprova si la cua està buida i torna el seu estat.
  3. prioritat_cua :: top (): Retorna una referència a l'element superior de la cua de prioritat.
  4. prioritat_cua :: push (): Afegeix un element al final de la cua de prioritat.
  5. prioritat_cua :: pop (): Elimina el primer element de la cua de prioritat.
  6. prioritat_cua :: swap (): S'utilitza per canviar el contingut d'una cua de prioritat per una altra del mateix tipus i mida.
  7. tipus de valor de cua prioritària: El tipus de valor proporciona el tipus de l'element emmagatzemat dins d'una cua de prioritat. Això també actua com a sinònim del paràmetre de plantilla.
  8. prioritat_cua :: emplace (): S’utilitza per inserir un element nou al contenidor de la cua prioritària a la part superior de la cua.

Al següent programa, veurem la funcionalitat de la cua de prioritat a STL en C ++.

#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << ' '; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << ' Top element of the queue(pq.top()): ' << pq.top(); cout << ' The priority queue pq is : '; displaypq(pq); cout << ' Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; }

Sortida:

programari per espiar telèfons mòbils

Mida de la cua (pq.size ()): 5
Element superior de la cua (pq.top ()): 9
La cua de prioritat pq és: 9 7 5 3 1
Cua de prioritat, després de l'operació pq.pop (): 7 5 3 1

Implementació de Java per a la cua de prioritat

La cua de prioritat a Java és una cua especial on tots els elements de la cua s’ordenen segons un ordre natural o un ordre personalitzat mitjançant un comparador subministrat amb la cua.

Una cua de prioritat a Java es veu com es mostra a continuació:

Implementació de Java per a la cua de prioritats

A la cua de prioritat de Java, els elements estan disposats de manera que l’element mínim es troba a la part davantera de la cua i l’element més gran es troba a la part posterior de la cua. Per tant, quan eliminem l’element de la cua de prioritat, sempre és l’element més petit que s’elimina.

La classe que implementa la cua de prioritat a Java és 'PriorityQueue' i forma part del marc de col·leccions de Java. Implementa la interfície 'Cua' de Java.

A continuació es mostra la jerarquia de classes per a la classe Java PriorityQueue.

jerarquia de classes per a la classe Java PriorityQueue

A continuació es mostra un exemple de funcionalitat de la cua de prioritat amb enters com a elements a Java.

import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println(' After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println(' After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( ' Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i

Sortida:

peek () :: Valor del cap: 1
La cua de prioritat:
1 3 5 7
Després de la funció poll (), cua de prioritat:
3 juliol 5
Després de la funció Elimina (5), feu la cua de prioritat:
març 7
La cua de prioritat conté 3 ?: cert
Elements de matriu:
Valor: 3
Valor: 7

Al programa anterior, fem servir la classe PriorityQueue de Java per crear un objecte de PriorityQueue que contingui un objecte Integer. Afegim elements a la cua mitjançant la funció 'afegir'. A continuació, es crida a la funció poll () i elimina l'element de la part davantera de la cua que és l'element menys important.

De nou anomenem la funció 'remove ()' que elimina l'element especificat com a paràmetre de la cua. També fem servir la funció 'Contains ()' per comprovar si hi ha un element concret a la cua. Finalment, convertim la cua en un objecte de matriu mitjançant la funció “toArray ()”.

Aplicació

  • Gestors d'equilibri de càrrega i interruptors del sistema operatiu: Funcions del sistema operatiu com l’equilibri de càrrega i la manipulació d’interrupcions s’implementen mitjançant cues prioritàries. L’activitat d’equilibri de càrrega programa els recursos amb la màxima prioritat per tal de portar efectivament el nostre equilibri de càrrega. La gestió de les interrupcions es realitza mantenint les interrupcions amb la màxima prioritat. Aquesta funcionalitat es pot implementar eficaçment utilitzant les cues de prioritat.
  • Encaminament: L’encaminament és una funció que s’utilitza per encaminar els recursos de la xarxa de manera que obtenim el màxim rendiment amb un temps d’inversió mínim. Això també es pot implementar mitjançant la cua de prioritat.
  • Urgències hospitalàries: En una sala d’urgències d’un hospital, s’atén els pacients segons la gravetat de l’estat del pacient. Això es pot simular mitjançant cues de prioritat.
  • Algoritme de camí més curt de Dijkstra: Aquí el gràfic s’emmagatzema com a llista d’adjacències i podem utilitzar una cua de prioritat per extreure el límit mínim ponderat de la llista d’adjacències de manera eficient per implementar l’algorisme de camí més curt de Dijkstra.
  • La cua de prioritat també es pot utilitzar per emmagatzemar claus de node i extreure el node de claus mínim mentre s’implementa l’arbre d’extensió.

Conclusió

Les cues prioritàries no són altra cosa que l'extensió de la cua. Però, a diferència de les cues que afegeixen / eliminen elements mitjançant l'enfocament FIFO, a la cua de prioritat els elements s'eliminen de la cua segons la prioritat. Per tant, cada element de la cua s’associa a una prioritat i l’element amb la màxima prioritat és el primer que es treu de la cua.

La cua de prioritat té tres operacions principals, és a dir, insert (), getHighestPriority () i deleteHighestPriority (). La cua de prioritat es pot implementar mitjançant matrius o llista enllaçada, però el funcionament no és molt eficient. La cua prioritària també es pot implementar mitjançant munts i el rendiment és molt més ràpid.

A C ++, també tenim una classe de contenidors que implementa la funcionalitat d’una cua de prioritat. A Java, hi ha una classe built-in priority_queue que proporciona la funcionalitat d'una cua de prioritat.

La cua de prioritats s'utilitza principalment en aplicacions que requereixen que els elements es processin segons la prioritat. Per exemple, s’utilitza en la manipulació d’interrupcions.

El nostre proper tutorial explorarà tot sobre la cua circular, que és una altra extensió de la cua.

=> Visiteu aquí el curs complet C ++ d’experts.

Lectura recomanada

^