Meniu

Structura de date a cozii prioritare în C ++ cu ilustrație

  • Principal
  • Alte
  • Structura de date a cozii prioritare în C ++ cu ilustrație

priority queue data structure c with illustration

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Introducere în coada prioritară în C ++ cu ilustrație.

Priority Queue este o extensie a cozii pe care am discutat-o ​​în ultimul nostru tutorial.

Este similar cu coada în anumite aspecte și totuși diferă de coada obișnuită în următoarele puncte:

  • Fiecare element din coada de prioritate este asociat cu o prioritate.
  • Elementul cu cea mai mare prioritate este primul element care trebuie eliminat din coadă.
  • Dacă mai multe elemente au aceeași prioritate, atunci se ia în considerare ordinea lor în coadă.

=> Faceți clic aici pentru seria Absolute C ++ Training.

Coadă prioritară în C ++

Putem vizualiza coada prioritară ca o versiune modificată a cozii, cu excepția faptului că atunci când elementul urmează să fie scos din coadă, elementul cu cea mai mare prioritate este preluat mai întâi. Așadar, preferăm să folosim cozile prioritare în loc de cozi atunci când trebuie să procesăm elementele pe baza priorității.

Ce veți învăța:

Operațiuni de bază

Să discutăm câteva dintre operațiunile de bază acceptate de coada de prioritate.

  • Inserați (element, prioritate): Inserează un element în coada de prioritate cu o prioritate dată.
  • getHighestPriority (): Returnează un articol cu ​​cea mai mare prioritate.
  • deleteHighestPriority (): Elimină un element cu cea mai mare prioritate.

În afară de operațiile de mai sus, putem folosi și operațiile de coadă normale, cum ar fi isEmpty (), isFull () și peek ().

Ilustrare

Să vedem o ilustrare a cozii prioritare. În scopul simplității, vom folosi caractere ASCII ca elemente în coada de prioritate. Cu cât valoarea ASCII este mai mare, cu atât este mai mare prioritatea.

Stare inițială - Coadă de prioritate (PQ) - {} => gol

ilustrarea cozii prioritare

Din ilustrația de mai sus, vedem că operația de inserare este similară cu o coadă obișnuită. Dar când apelăm „deleteHighestPriority” pentru coada de prioritate, elementul cu cea mai mare prioritate este eliminat mai întâi.

Prin urmare, prima dată când apelăm această funcție, elementul O este eliminat, în timp ce a doua oară, elementul M este eliminat, deoarece are prioritate mai mare decât G și A.

Implementarea cozilor prioritare în C ++

Cozile prioritare pot fi implementate folosind:

# 1) Matrice / liste legate

Putem implementa cozile prioritare folosind tablouri și aceasta este cea mai simplă implementare pentru cozile prioritare.

Pentru a reprezenta elementele din coada de prioritate, putem doar să declarăm o structură după cum urmează:

struct pq_item{ int item; int priority; };

Am declarat și prioritatea pentru fiecare articol.

Pentru a insera un element nou în coada de prioritate trebuie pur și simplu să inserăm elementul la sfârșitul matricei.

Pentru a obține elementul din coadă folosind getHighestPriority (), trebuie să traversăm matricea de la început și să returnăm elementul cu cea mai mare prioritate.

În mod similar, pentru a elimina elementul din coadă folosind operațiunea deleteHighestPriority, trebuie să traversăm întreaga matrice și să ștergem elementul cu cea mai mare prioritate. Apoi mutați toate celelalte elemente după elementul șters, cu o poziție înapoi.

De asemenea, putem implementa coada prioritară utilizând o listă legată. Putem efectua toate operațiunile într-un mod similar, cum ar fi tablourile. Singura diferență este că nu trebuie să mutăm elementele după ce am apelat deleteHighestPriority.

# 2) Mormane

Utilizarea grămezilor pentru a implementa o coadă prioritară este cel mai eficient mod și oferă o performanță mult mai bună în comparație cu listele și matricile legate. Spre deosebire de lista și matricea legată, implementarea heap durează O (logn) timp pentru operațiile de inserare și ștergere a cozii de prioritate. Operațiunea, getHighestPriority necesită O (1) timp.

# 3) Coadă de prioritate încorporată în biblioteca de șabloane standard (STL) în C ++

În C ++, avem o coadă prioritară ca clasă de adaptare la container, proiectată în așa fel încât cel mai înalt element este primul element din coadă și toate elementele sunt în ordinea descrescătoare.

Astfel fiecare element din coada de prioritate are o prioritate fixă.

Avem clasă în STL, care conține implementarea cozii prioritare.

Diferitele operații acceptate de coada de prioritate sunt următoarele:

  1. prioritate_coadă :: mărime (): Returnează dimensiunea cozii.
  2. prioritate_coadă :: gol (): Verifică dacă coada este goală și își returnează starea.
  3. prioritate_coadă :: top (): Returnează o referință la cel mai de sus element al cozii de prioritate.
  4. prioritate_coadă :: push (): Adaugă un element la sfârșitul cozii prioritare.
  5. prioritate_coadă :: pop (): Elimină primul element din coada de prioritate.
  6. prioritate_coadă :: swap (): Folosit pentru a schimba conținutul unei cozi prioritare cu altul de același tip și dimensiune.
  7. tipul valorii cozii prioritare: Tipul de valoare oferă tipul elementului stocat într-o coadă prioritară. Aceasta acționează și ca sinonim pentru parametrul șablon.
  8. prioritate_coadă :: emplace (): Folosit pentru a insera un element nou în containerul cozii prioritare din partea de sus a cozii.

În următorul program, vom vedea funcționalitatea cozii de prioritate în STL în 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; }

Ieșire:

cum deschid un torrent

Dimensiunea cozii (pq.size ()): 5
Elementul superior al cozii (pq.top ()): 9
Coada prioritară pq este: 9 7 5 3 1
Coadă prioritară, după operația pq.pop (): 7 5 3 1

Implementarea Java pentru coada prioritară

Coada prioritară în java este o coadă specială în care toate elementele din coadă sunt ordonate în funcție de comanda naturală sau de comanda personalizată utilizând un comparator furnizat împreună cu coada.

O coadă prioritară în Java arată așa cum se arată mai jos:

Implementare Java pentru coada prioritară

În coada de prioritate Java, elementele sunt aranjate astfel încât cel mai mic element să fie în partea din față a cozii și cel mai mare element să fie în partea din spate a cozii. Deci, atunci când eliminăm elementul din coada de prioritate, este întotdeauna cel mai mic element care este eliminat.

Clasa care implementează coada prioritară în Java este „PriorityQueue” și face parte din cadrul colecțiilor Java. Implementează interfața „Queue” a Java.

Urmează ierarhia de clase pentru clasa Java PriorityQueue.

ierarhia de clase pentru clasa Java PriorityQueue

Dat mai jos este un exemplu de funcționalitate coadă prioritară cu numere întregi ca elemente în 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

Ieșire:

peek () :: Valoarea capului: 1
Coada prioritară:
1 3 5 7
După funcția poll (), coada prioritară:
3 7 5
După funcția Eliminare (5), coadă prioritară:
3 7
Coada prioritară conține 3 ?: adevărat
Elemente matrice:
Valoare: 3
Valoare: 7

În programul de mai sus, folosim clasa Java PriorityQueue pentru a crea un obiect PriorityQueue care conține un obiect Integer. Adăugăm elemente în coadă folosind funcția „adăugați”. Apoi se apelează funcția poll () și șterge elementul din partea din față a cozii, care se întâmplă să fie cel mai mic element.

Din nou numim funcția „remove ()” care elimină elementul specificat ca parametru din coadă. De asemenea, folosim funcția „Conține ()” pentru a verifica dacă un anumit element este prezent în coadă. În cele din urmă, convertim coada într-un obiect matrice folosind funcția „toArray ()”.

Cerere

  • Manevrele de echilibrare a sarcinii și întreruperi ale sistemului de operare Funcțiile sistemului de operare precum echilibrarea încărcării și gestionarea întreruperilor sunt implementate utilizând cozi prioritare. Activitatea de echilibrare a încărcării programează resursele cu cea mai mare prioritate pentru a ne efectua echilibrarea încărcăturii. Manipularea întreruperilor se realizează prin deservirea întreruperilor cu cea mai mare prioritate. Această funcționalitate poate fi implementată eficient folosind cozile prioritare.
  • Rutare: Rutarea este o funcție care este utilizată pentru a direcționa resursele rețelei, astfel încât să obținem un debit maxim cu un timp de răspuns minim. Acest lucru poate fi implementat și utilizând coada de prioritate.
  • Urgența spitalului: Într-o cameră de urgență a spitalului, pacienții sunt tratați în funcție de cât de gravă este starea pacientului. Acest lucru poate fi simulat folosind cozi prioritare.
  • Cel mai scurt algoritm al căii Dijkstra: Aici graficul este stocat ca o listă de adiacență și putem folosi o coadă de prioritate pentru a extrage eficient marginea minimă ponderată din lista de adiacență pentru a implementa cel mai scurt algoritm al căii Dijkstra.
  • Coada prioritară poate fi, de asemenea, utilizată pentru a stoca cheile nodului și a extrage nodul cheie minim în timpul implementării arborelui de întindere.

Concluzie

Cozile prioritare nu sunt altceva decât extensia cozii. Dar, spre deosebire de cozile care adaugă / elimină elemente folosind abordarea FIFO, în coada prioritară elementele sunt eliminate din coadă în funcție de prioritate. Astfel, fiecare element din coadă este asociat cu o prioritate, iar elementul cu cea mai mare prioritate este primul care este scos din coadă.

Coada de prioritate are trei operații principale, adică insert (), getHighestPriority () și deleteHighestPriority (). Coada prioritară poate fi implementată folosind tablouri sau listă legată, dar funcționarea nu este foarte eficientă. Coada prioritară poate fi, de asemenea, implementată folosind grămezi, iar performanța este mult mai rapidă.

În C ++, avem și o clasă de containere care implementează funcționalitatea unei cozi prioritare. În Java, există o clasă de prioritate coadă încorporată care oferă funcționalitatea unei cozi de prioritate.

Coada de prioritate este utilizată în principal în aplicații care necesită prelucrarea articolelor în funcție de prioritate. De exemplu, este utilizat în tratarea întreruperilor.

Următorul nostru tutorial va explora totul despre coada circulară, care este încă o extensie a cozii.

=> Vizitați aici pentru cursul complet C ++ de la experți.

Lectură recomandată

^