Menu

Štruktúra dát prioritného frontu v C ++ s ilustráciou

  • Hlavná
  • Iné
  • Štruktúra dát prioritného frontu v C ++ s ilustráciou

priority queue data structure c with illustration

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Úvod do prioritného frontu v C ++ s ilustráciou.

Prioritný front je rozšírením frontu, o ktorom sme hovorili v našom poslednom tutoriále.

Je to v určitých aspektoch podobné frontu, a napriek tomu sa líši od bežného frontu v nasledujúcich bodoch:

  • Každá položka vo fronte priorít je priradená k priorite.
  • Položka s najvyššou prioritou je prvou položkou, ktorá sa odstráni z poradia.
  • Ak má viac ako jedna položka rovnakú prioritu, potom sa zohľadní ich poradie vo fronte.

=> Kliknutím sem zobrazíte sériu školení Absolute C ++.

Prioritný front v C ++

Môžeme si predstaviť prioritný front ako upravenú verziu frontu, až na to, že keď sa má položka z fronty odobrať, najskôr sa načíta položka s najvyššou prioritou. Keď teda potrebujeme spracovať položky na základe priority, uprednostňujeme použitie frontov namiesto frontov.

Čo sa dozviete:

Základné operácie

Poďme diskutovať o niektorých základných operáciách podporovaných prioritným frontom.

  • Vložiť (položka, priorita): Vloží položku do frontu priorít s danou prioritou.
  • getHighestPriority (): Vráti položku s najvyššou prioritou.
  • deleteHighestPriority (): Odstráni položku s najvyššou prioritou.

Okrem vyššie uvedených operácií môžeme použiť aj bežné operácie frontu ako isEmpty (), isFull () a peek ().

Ilustrácia

Pozrime sa na ilustráciu prioritného frontu. Pre zjednodušenie budeme ako položky vo fronte priorít používať znaky ASCII. Čím vyššia je hodnota ASCII, tým vyššia je priorita.

Počiatočný stav - Prioritný front (PQ) - {} => prázdny

ilustrácia prioritného frontu

Z vyššie uvedeného obrázku vidíme, že operácia vloženia je podobná bežnému frontu. Ale keď pre prioritný front zavoláme „deleteHighestPriority“, najskôr sa odstráni prvok s najvyššou prioritou.

Preto prvý raz, keď voláme túto funkciu, je položka O odstránená, zatiaľ čo druhýkrát je položka M odstránená, pretože má vyššiu prioritu ako G a A.

Implementácia prioritných front v C ++

Prioritné fronty je možné implementovať pomocou:

# 1) Polia / prepojené zoznamy

Prioritné fronty môžeme implementovať pomocou polí a toto je najjednoduchšia implementácia pre prioritné fronty.

Na reprezentáciu položiek v prioritnom rade môžeme deklarovať nasledujúcu štruktúru:

struct pq_item{ int item; int priority; };

Pre každú položku sme tiež deklarovali prioritu.

Ak chcete vložiť novú položku do fronty priorít, musíme ju jednoducho vložiť na koniec poľa.

Ak chcete získať prvok z frontu pomocou funkcie getHighestPriority (), musíme pole prejsť od začiatku a vrátiť položku s najvyššou prioritou.

Podobne, aby sme položku odstránili z frontu pomocou operácie deleteHighestPriority, musíme prejsť celé pole a vymazať položku s najvyššou prioritou. Potom posuňte všetky ostatné prvky za odstránenú položku o jednu pozíciu dozadu.

Frontu priorít môžeme implementovať aj pomocou prepojeného zoznamu. Všetky operácie môžeme vykonávať podobným spôsobom ako polia. Jediný rozdiel je v tom, že po vyvolaní príkazu deleteHighestPriority nemusíme posúvať prvky.

# 2) Hromady

Používanie hromad na implementáciu prioritného frontu je najefektívnejším spôsobom a poskytuje oveľa lepší výkon v porovnaní s prepojenými zoznamami a poľami. Na rozdiel od prepojeného zoznamu a poľa, implementácia haldy trvá O (logn) času pre operácie vloženia a odstránenia prioritného frontu. Získajte operáciu, funkcia getHighestPriority trvá O (1).

# 3) Integrovaný prioritný rad v knižnici štandardných šablón (STL) v C ++

V C ++ máme prioritný front ako kontajnerová adaptívna trieda, ktorá je navrhnutá tak, že najvyšší prvok je prvý prvok vo fronte a všetky prvky sú v zmenšujúcom sa poradí.

Každá položka vo fronte priorít má teda pevnú prioritu.

Máme triedu v STL, ktorá obsahuje implementáciu prioritného frontu.

Rôzne operácie podporované frontom priorít sú nasledujúce:

  1. priority_queue :: size (): Vráti veľkosť frontu.
  2. priority_queue :: empty (): Skontroluje, či je rad prázdny, a vráti jeho stav.
  3. priority_queue :: top (): Vráti odkaz na najvyšší prvok prioritného frontu.
  4. priority_queue :: push (): Pridá položku na koniec prioritného frontu.
  5. priority_queue :: pop (): Odstráni prvý prvok z frontu priorít.
  6. priority_queue :: swap (): Používa sa na výmenu obsahu jedného prioritného frontu s iným frontom rovnakého typu a veľkosti.
  7. typ hodnoty prioritného frontu: Typ hodnoty udáva typ prvku uloženého vo fronte priorít. Funguje to tiež ako synonymum pre parameter šablóny.
  8. priority_queue :: emplace (): Používa sa na vloženie nového prvku do kontajnera prioritných frontov v hornej časti frontu.

V ďalšom programe uvidíme funkčnosť prioritného frontu v STL v 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; }

Výkon:

základné otázky a odpovede na otázky java pre skúsených

Veľkosť poradia (pq.size ()): 5
Najlepší prvok v poradí (pq.top ()): 9
Prioritný front pq je: 9 7 5 3 1
Prioritný rad po operácii pq.pop (): 7 5 3 1

Implementácia Java pre prioritný front

Prioritný front v Jave je špeciálny front, v ktorom sú všetky prvky vo fronte zoradené podľa prirodzeného poradia alebo podľa vlastného poradia pomocou komparátora dodaného s frontom.

Poradie prioritných front v prostredí Java vyzerá takto:

Implementácia Java pre prioritný front

Vo fronte priorít Java sú prvky usporiadané tak, že najmenší prvok je v prednej časti frontu a najväčší prvok je v zadnej časti frontu. Keď teda odstránime prvok z frontu priorít, vždy sa odstráni najmenší prvok.

Trieda, ktorá implementuje prioritný front v Jave, je „PriorityQueue“ a je súčasťou zbierkového rámca Javy. Implementuje rozhranie Java „Queue“.

Nasleduje hierarchia tried pre triedu Java PriorityQueue.

hierarchia tried pre triedu Java PriorityQueue

Nižšie je uvedený príklad funkčnosti prioritného frontu s celými číslami ako položkami v Jave.

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

Výkon:

peek () :: Hlavová hodnota: 1
Poradie priorít:
1 3 5 7
Po funkcii poll (), prioritný front:
3 7 5
Po funkcii Odstrániť (5), prioritný front:
3 7
Prioritná fronta obsahuje 3 ?: pravda
Prvky poľa:
Hodnota: 3
Hodnota: 7

Vo vyššie uvedenom programe používame triedu Java PriorityQueue na vytvorenie objektu PriorityQueue, ktorý obsahuje objekt Integer. Prvky do frontu pridávame pomocou funkcie „pridať“. Potom sa zavolá funkcia poll (), ktorá vymaže prvok spredu frontu, ktorý je najmenším prvkom.

Opäť voláme funkciu „remove ()“, ktorá odstráni prvok zadaný ako parameter z frontu. Funkciu „Obsahuje ()“ tiež používame na kontrolu, či sa vo fronte nachádza konkrétny prvok. Nakoniec rad prevedieme na objekt poľa pomocou funkcie „toArray ()“.

Aplikácia

  • Vyrovnávanie zaťaženia operačného systému a obslužné rutiny prerušenia: Funkcie operačného systému ako vyvažovanie záťaže a manipulácia s prerušeniami sa implementujú pomocou prioritných frontov. Aktivita vyrovnávania zaťaženia plánuje zdroje s najvyššou prioritou, aby mohla efektívne vykonávať vyváženie záťaže. Spracovanie prerušenia sa vykonáva obsluhou prerušenia s najvyššou prioritou. Túto funkcionalitu je možné efektívne implementovať pomocou prioritných frontov.
  • Smerovanie: Smerovanie je funkcia, ktorá sa používa na smerovanie sieťových prostriedkov tak, aby sme dosiahli maximálnu priepustnosť s minimálnym časom obratu. To možno implementovať aj pomocou prioritného frontu.
  • Núdzová nemocnica: Na nemocničnej pohotovosti sú pacienti sledovaní podľa toho, aký závažný je stav pacienta. To je možné simulovať pomocou prioritných front.
  • Algoritmus najkratšej cesty Dijkstra: Tu je graf uložený ako zoznam adjacency a môžeme pomocou prioritnej fronty efektívne extrahovať minimálnu váženú hranu zo zoznamu adjacency a implementovať Dijkstraov najkratší algoritmus cesty.
  • Prioritný front možno použiť aj na ukladanie kľúčov uzlov a extrahovanie minimálneho uzla kľúča pri implementácii spanning tree.

Záver

Prioritné fronty nie sú nič iné ako rozšírenie frontu. Ale na rozdiel od frontov, ktoré pridávajú / odoberajú položky pomocou prístupu FIFO, v prioritnom fronte sú položky z frontu odstránené podľa priority. Každá položka vo fronte je teda spojená s prioritou a položka s najvyššou prioritou je prvou, ktorá bola z fronty vyradená.

Fronta priorít má tri hlavné operácie, tj. Insert (), getHighestPriority () a deleteHighestPriority (). Prioritný front je možné implementovať pomocou polí alebo prepojeného zoznamu, ale práca nie je veľmi efektívna. Prioritný front je možné implementovať aj pomocou hromadných súborov a výkon je oveľa rýchlejší.

V C ++ máme aj triedu kontajnera, ktorá implementuje funkčnosť prioritného frontu. V Jave je zabudovaná trieda prioritná_kategória, ktorá poskytuje funkčnosť prioritného frontu.

Fronta priority sa používa hlavne v aplikáciách, ktoré vyžadujú spracovanie položiek podľa priority. Napríklad, používa sa pri narušení.

Náš nadchádzajúci tutoriál bude skúmať všetko o kruhovom fronte, ktorý je ďalším rozšírením frontu.

=> Navštívte tu kompletný kurz C ++ od odborníkov.

Odporúčané čítanie

^