Prioritný front je abstraktný dátový typ, ktorý sa správa podobne ako normálny front s tým rozdielom, že každý prvok má určitú prioritu, t. j. prvok s najvyššou prioritou bude v prioritnom rade na prvom mieste. Priorita prvkov v prioritnom fronte určí poradie, v ktorom budú prvky odstránené z prioritného frontu.
Prioritný front podporuje iba porovnateľné prvky, čo znamená, že prvky sú usporiadané vzostupne alebo zostupne.
reverzný reťazec java
Predpokladajme napríklad, že máme nejaké hodnoty ako 1, 3, 4, 8, 14, 22 vložené do prioritného frontu s usporiadaním uloženým hodnotám od najmenšieho po najväčšiu. Preto číslo 1 bude mať najvyššiu prioritu, zatiaľ čo číslo 22 bude mať najnižšiu prioritu.
Charakteristiky prioritného frontu
Prioritný front je rozšírenie frontu, ktoré obsahuje nasledujúce charakteristiky:
- Každý prvok v prioritnom fronte má priradenú nejakú prioritu.
- Prvok s vyššou prioritou bude vymazaný pred odstránením s nižšou prioritou.
- Ak majú dva prvky v prioritnom rade rovnakú prioritu, budú usporiadané podľa princípu FIFO.
Poďme pochopiť prioritný front prostredníctvom príkladu.
Máme prioritný front, ktorý obsahuje nasledujúce hodnoty:
1, 3, 4, 8, 14, 22
Všetky hodnoty sú usporiadané vo vzostupnom poradí. Teraz budeme sledovať, ako bude prioritný front vyzerať po vykonaní nasledujúcich operácií:
Typy prioritného frontu
Existujú dva typy prioritných frontov:
Zastúpenie prioritného frontu
Teraz uvidíme, ako reprezentovať prioritný front prostredníctvom jednosmerného zoznamu.
Prioritný front vytvoríme pomocou nižšie uvedeného zoznamu, v ktorom INFO zoznam obsahuje dátové prvky, PRN zoznam obsahuje čísla priority každého dátového prvku dostupného v INFO zoznam a LINK v podstate obsahuje adresu nasledujúceho uzla.
Vytvorme prioritný front krok za krokom.
java sort arraylist
V prípade prioritného frontu sa za vyššiu prioritu považuje číslo s nižšou prioritou, t.j. nižšie číslo priority = vyššia priorita.
Krok 1: Číslo s nižšou prioritou v zozname je 1, ktorého hodnota údajov je 333, takže bude vložené do zoznamu, ako je znázornené na obrázku nižšie:
Krok 2: Po vložení 333 má priorita číslo 2 vyššiu prioritu a hodnoty údajov priradené k tejto priorite sú 222 a 111. Tieto údaje sa teda vložia na základe princípu FIFO; preto sa najprv pridá 222 a potom 111.
Krok 3: Po vložení prvkov priority 2 je najbližšie vyššie prioritné číslo 4 a dátové prvky spojené so 4 prioritnými číslami sú 444, 555, 777. V tomto prípade by sa prvky vložili na základe princípu FIFO; preto sa najprv pridá 444, potom 555 a potom 777.
Krok 4: Po vložení prvkov priority 4 je najbližšie vyššie číslo priority 5 a hodnota spojená s prioritou 5 je 666, takže bude vložená na koniec frontu.
Implementácia prioritného frontu
Prioritný front môže byť implementovaný štyrmi spôsobmi, ktoré zahŕňajú polia, prepojený zoznam, štruktúru údajov haldy a binárny vyhľadávací strom. Štruktúra údajov haldy je najefektívnejším spôsobom implementácie prioritného frontu, preto v tejto téme implementujeme prioritný front pomocou štruktúry údajov haldy. Teraz najprv pochopíme dôvod, prečo je halda najefektívnejším spôsobom spomedzi všetkých ostatných dátových štruktúr.
Analýza zložitosti pomocou rôznych implementácií
| Implementácia | pridať | Odstrániť | nahliadnuť |
| Prepojený zoznam | O(1) | O(n) | O(n) |
| Binárna halda | O(logn) | O(logn) | O(1) |
| Binárny vyhľadávací strom | O(logn) | O(logn) | O(1) |
Čo je Heap?
Halda je stromová dátová štruktúra, ktorá tvorí úplný binárny strom a spĺňa vlastnosť haldy. Ak je A nadradený uzol B, potom A je usporiadané vzhľadom na uzol B pre všetky uzly A a B v halde. Znamená to, že hodnota nadradeného uzla môže byť väčšia alebo rovná hodnote podriadeného uzla, alebo hodnota nadradeného uzla môže byť menšia alebo rovná hodnote podriadeného uzla. Preto môžeme povedať, že existujú dva typy kôp:
Obidve haldy sú binárnou haldou, pretože každá má presne dva podriadené uzly.
Prioritné operácie frontu
Bežné operácie, ktoré môžeme vykonávať na prioritnom fronte, sú vkladanie, mazanie a nahliadnutie. Pozrime sa, ako môžeme zachovať štruktúru údajov haldy.
Ak vložíme prvok do prioritného frontu, presunie sa do prázdneho slotu pohľadom zhora nadol a zľava doprava.
ako zistiť veľkosť monitora
Ak prvok nie je na správnom mieste, potom sa porovná s nadradeným uzlom; ak sa zistí nefunkčnosť, prvky sa vymenia. Tento proces pokračuje, kým nie je prvok umiestnený v správnej polohe.
Ako vieme, v maximálnej halde je maximálnym prvkom koreňový uzol. Keď odstránime koreňový uzol, vytvorí sa prázdny slot. Posledný vložený prvok bude pridaný do tohto prázdneho slotu. Potom sa tento prvok porovná s podriadenými uzlami, t. j. ľavým a pravým potomkom, a vymení sa s menším z dvoch. Stále sa pohybuje po strome, kým sa vlastnosť haldy neobnoví.
Aplikácie prioritného frontu
Nasledujú aplikácie prioritného frontu:
- Používa sa v Dijkstrovom algoritme najkratšej cesty.
- Používa sa v primovom algoritme
- Používa sa v technikách kompresie údajov, ako je Huffmanov kód.
- Používa sa pri triedení haldy.
- Používa sa aj v operačnom systéme, ako je plánovanie priorít, vyrovnávanie záťaže a manipulácia s prerušením.
Program na vytvorenie prioritného frontu pomocou binárnej maximálnej haldy.
#include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i > 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong> </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>