java priority queue tutorial implementation examples
Tento výukový program vysvetľuje prioritný front Java a súvisiace koncepty ako komparátor, minimálna a maximálna prioritná fronta spolu s jeho implementáciou s príkladmi:
Dátová štruktúra prioritného frontu je špeciálny front, v ktorom prvky nie sú prítomné podľa poradia FIFO, ale podľa prírodných prvkov alebo ľubovoľného vlastného komparátora použitého pri vytváraní frontu.
=> Tu si pozrite príručku Java Beginners Guide.
Čo sa dozviete:
Prioritný front v Jave
V prioritnom fronte má predná časť frontu najmenej prvkov podľa prirodzeného usporiadania a zadná strana ukazuje na najväčší prvok vo fronte.
Nižšie je uvedený príklad prioritného frontu pozostávajúci z čísel.
pl sql pohovor otázky s odpoveďami
Keď je teda prvok odstránený z prioritného frontu zobrazeného vyššie, bude to najmenej prvku.
Podobne pre front s abecednou prioritou sa budú brať do úvahy hodnoty ASCII a prvky frontu sa zoradia podľa hodnôt ASCII.
Nižšie sú uvedené niektoré z hlavných charakteristík fronty priorít:
- PriorityQueue je neviazaný front.
- PriorityQueue nepovoľuje nulové hodnoty.
- Pre neporovnateľné objekty nemôžeme vytvoriť prioritný front.
- PriorityQueue dedí z tried ako AbstractQueue, AbstractCollection, Collection a Object.
- Hlava alebo predok frontu obsahuje najmenej prvkov podľa prirodzeného usporiadania.
- Implementácia prioritného frontu nie je bezpečná pre vlákna. Pokiaľ teda požadujeme synchronizovaný prístup, mali by sme použiť PriorityBlockingQueue.
Trieda PriorityQueue dedí rozhranie Java Queue Interface a je súčasťou balíka java.util.
Všeobecné vyhlásenie triedy PriorityQueue je uvedené nižšie:
public class PriorityQueue extends AbstractQueue implements SerializableNasledujúci diagram zobrazuje hierarchiu tried pre triedu PriorityQueue.
Časová zložitosť prioritného frontu
- Časová zložitosť prioritného frontu pre metódy vkladania (zaradenia do fronty) a vymazania (odstránenia z frontu) je O (log (n)).
- Prioritná fronta má lineárnu časovú zložitosť pre odstránenie a obsahuje aj metódy.
- Metódy, ktoré načítajú prvky prioritného frontu, majú neustálu časovú zložitosť.
Príklad prioritného frontu v prostredí Java
Nasledujúci program demonštruje jednoduchú PriorityQueue v Jave. Vytvoríme objekt triedy PriorityQueue, pridáme doň hodnoty a potom zobrazíme obsah frontu pomocou Iterátora.
import java.util.*; class Main{ public static void main(String args()){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } Výkon:
Metódy API prioritného frontu Java
Konštruktéri:
| Prototyp konštruktéra | Popis | |
|---|---|---|
| nakuknúť | E nahliadnuť () | Vráti hlavičku frontu bez odstránenia prvku. |
| PriorityQueue () | Predvolený konštruktor, ktorý vytvára objekt PriorityQueue s počiatočnou kapacitou ako 1. | |
| PriorityQueue (zbierka c) | Vytvorí objekt PriorityQueue s počiatočnými prvkami z danej kolekcie c. | |
| PriorityQueue (int initialCapacity) | Vytvorí objekt PriorityQueue s danou „initialCapacity“. Prvky sa objednávajú podľa prirodzeného usporiadania. | |
| PriorityQueue (int initialCapacity, komparátor komparátor) | Vytvorí objekt PriorityQueue s danou „initialCapacity“. Prvky sú zoradené podľa daného komparátora. | |
| PriorityQueue (PriorityQueue c) | Vytvorí objekt PriorityQueue z iného objektu PriorityQueue daného c. | |
| PriorityQueue (SortedSet c) | Vytvorí objekt PriorityQueue z SortedSet danej c. |
Metódy
| Metóda | Metóda Prototyp | Popis |
|---|---|---|
| pridať | boolovský prírastok (E e) | Pridá prvok e do PriorityQueue. |
| jasný | prázdne miesto jasné () | Vymaže prioritnú frontu odstránením všetkých prvkov. |
| komparátor | Porovnávací porovnávač () | Vráti vlastný komparátor použitý na zoradenie prvkov vo fronte. |
| obsahuje | boolean obsahuje (Objekt o) | Skontroluje, či PriorityQueue obsahuje daný prvok o. Ak áno, vráti hodnotu true. |
| iterátor | Iteratoriterator () | Metóda získania iterátora pre danú PriorityQueue. |
| ponuka | boolovská ponuka (E e) | Vložte daný prvok e do PriorityQueue. |
| anketa | E anketa () | Odstráni a vráti hlavičku frontu. Ak je rad prázdny, vráti hodnotu null. |
| odstrániť | boolean remove (Objekt o) | Odstráni inštanciu daného prvku o, ak je vo fronte. |
| veľkosť | veľkosť int () | Vráti veľkosť alebo počet prvkov v tejto PriorityQueue. |
| toArray | Objekt () toArray () | Vráti reprezentáciu poľa danej PriorityQueue. |
| toArray | T () toArray (T () a) | Vráti reprezentáciu poľa pre daný prioritný front s rovnakým typom behu ako zadané pole a. |
Implementácia v Jave
Ukážme si vyššie uvedené metódy PriorityQueue pomocou programu Java.
import java.util.*; class Main { public static void main(String args()) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object() numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i Výkon:
najlepší bezplatný youtube downloader pre PC
Prioritný front v prostredí Java 8
Java 8 pridáva do triedy PriorityQueue ešte jednu metódu, tj. „Spliterator ()“.
Podrobnosti o tejto metóde sú uvedené nižšie.
Názov metódy: rozdeľovač
Prototyp metódy: verejný konečný Spliterator spliterator ()
Popis metódy: Táto metóda vytvára rozdeľovač nad prvkami PriorityQueue. Tento rozdeľovač je neskoro väzbový a rýchlo zlyháva.
Porovnávač prioritných front
Ako už bolo uvedené, prvky PriorityQueue sú prirodzene usporiadané. Ak chceme zmeniť poradie, mali by sme určiť komparátor a použiť ho pri vytváraní objektu PriorityQueue. PriorityQueue potom použije tento komparátor na zoradenie svojich prvkov.
Nižšie uvedený program Java demonštruje použitie vlastného komparátora na usporiadanie prvkov. V tomto programe definujeme nový vlastný komparátor, v rámci ktorého prepíšeme metódu „porovnania“. Porovnávacia metóda sa používa na zoradenie prvkov PriorityQueue podľa dĺžky.
import java.util.*; public class Main { public static void main(String() args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } Výkon:
Min. Prioritný front v Jave
Prirodzené zoradenie prioritného frontu má najmenší alebo najmenší prvok v čele frontu, a teda zoradenie stúpa. Toto sa nazýva „Min. Prioritný front“ so vzostupným poradím prvkov.
Nižšie uvedený program Java zobrazuje implementáciu frontu minimálnej priority v jazyku Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } Výkon:
Maximálny prioritný rad v Jave
Zatiaľ čo front s prioritou min má prvky vo vzostupnom poradí, front s maximálnou prioritou má prvky v zostupnom poradí, t. J. Vedúci frontu s prioritou Max vráti najväčší prvok v rade.
Nižšie uvedený program Java demonštruje rad maximálnych priorít v prostredí Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs Výkon:
Ako je uvedené v predchádzajúcom programe, aby sme zmenili prirodzené usporiadanie prvkov v rade priorít, musíme definovať vlastný komparátor.
často kladené otázky
Otázka 1) Čo je prioritný front v prostredí Java?
Odpoveď: Špeciálny front, v ktorom sú všetky prvky frontu zoradené podľa prirodzeného poradia alebo pomocou vlastného komparátora, sa nazýva prioritný front. Neriadi sa objednávkou FIFO.
Otázka 2) Ako nastavíte front s maximálnou prioritou v prostredí Java?
Odpoveď: Môžeme nastaviť Max Priority Queue v Jave pomocou vlastného komparátora tak, aby vedúci frontu vrátil najväčší prvok vo fronte.
Otázka č. 3) Umožňuje prioritný front duplikáty Javy?
Odpoveď: Áno. Prioritná fronta umožňuje duplicitné hodnoty.
Otázka č. 4) Je front s prioritou Java maximálny alebo minimálny?
Odpoveď: Štandardne je prioritný front v Jave minimálny prioritný front s prirodzeným usporiadaním. Aby to bolo maximum, musíme použiť vlastný komparátor, aby hlava frontu vrátila najväčší prvok vo fronte.
Otázka č. 5) Je zoradený prioritný front?
ako zvládať ťažké situácie v práci
Odpoveď: Predvolene je hlavička frontu zoradená a prioritná fronta má ako hlavičku najmenej prvkov. Zvyšok prvkov je na požiadanie objednaný.
Záver
Týmto sa dokončuje príručka o prioritných frontoch v jazyku Java. Prioritný front implementuje rozhranie frontu a je to špeciálny front, kde sú prvky usporiadané podľa prirodzeného poradia. Neriadi sa objednávkou FIFO. Na zmenu prirodzeného usporiadania frontu priorít môžeme použiť vlastný komparátor.
Prioritné fronty sa používajú hlavne na plánovanie tlačiarní, plánovanie úloh CPU atď. Halda (min. Alebo max.) Sa tiež implementuje pomocou prioritných frontov.
=> Prečítajte si sériu Easy Java Training Series.
Odporúčané čítanie
- Štruktúra dát prioritného frontu v C ++ s ilustráciou
- Prioritný front v STK
- Fronta Java - metódy fronty, implementácia frontu s príkladmi
- Štruktúra dát kruhového frontu C ++: implementácia a aplikácie
- Oboustranný front (Deque) v C ++ s príkladmi
- Dátová štruktúra frontu v C ++ s ilustráciou
- Stohy a fronty v STK
- Výukový program JAVA pre začiatočníkov: viac ako 100 praktických výučbových programov Java Video
