Menu

Výukový program pre prioritné fronty Java - Implementácia a príklady

  • Hlavná
  • Iné
  • Výukový program pre prioritné fronty Java - Implementácia a príklady

java priority queue tutorial implementation examples

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

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.

Prioritný front v Jave

Č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

Prioritný front - príklad

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 Serializable

Nasledujúci diagram zobrazuje hierarchiu tried pre triedu PriorityQueue.

Hierarchia tried pre triedu PriorityQueue.

Časová zložitosť prioritného frontu

  1. Časová zložitosť prioritného frontu pre metódy vkladania (zaradenia do fronty) a vymazania (odstránenia z frontu) je O (log (n)).
  2. Prioritná fronta má lineárnu časovú zložitosť pre odstránenie a obsahuje aj metódy.
  3. 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:

Výstup - príklad fronty

Metódy API prioritného frontu Java

Konštruktéri:

Prototyp konštruktéraPopis
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ódaMetóda PrototypPopis
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

výstup - Implementácia prioritného frontu

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:

Porovnávač prioritných front - výstup

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:

výstup - min. prioritný front v Jave

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:

nahrať

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

^