java priority queue tutorial implementation examples
Acest tutorial explică coada de prioritate Java și conceptele conexe precum Comparator, Min și Max Priority Queue împreună cu implementarea acestuia cu exemple:
Structura de date Priority Queue este o coadă specială în care elementele sunt prezente nu conform ordinii FIFO, ci în funcție de elementele naturale sau de orice comparator personalizat utilizat în timpul creării cozii.
=> Consultați aici Ghidul pentru începători Java.
Ce veți învăța:
Coadă prioritară în Java
În Priority Queue, partea din față a cozii are cele mai puține elemente conform ordonării naturale, iar partea din spate este îndreptată către cel mai mare element din coadă.
Un exemplu de coadă prioritară constând din numere este prezentat mai jos.
cum se scrie selector CSS în seleniu
Astfel, atunci când un element este eliminat din coada de prioritate afișată mai sus, atunci acesta va fi cel mai mic element.
În mod similar, pentru o coadă prioritară alfabetică, valorile ASCII vor fi luate în considerare, iar elementele cozii vor fi ordonate conform valorilor ASCII.
Mai jos sunt enumerate câteva dintre caracteristicile majore ale PriorityQueue:
- PriorityQueue este o coadă nelegată.
- PriorityQueue nu permite valori nule.
- Pentru obiectele care nu sunt comparabile, nu putem crea o coadă prioritară.
- PriorityQueue moștenește din clase precum AbstractQueue, AbstractCollection, Collection și Object.
- Capul sau fața cozii conține cel mai puțin element conform ordonării naturale.
- Implementarea cozii prioritare nu este sigură pentru fire. Astfel, dacă dorim acces sincronizat, ar trebui să folosim PriorityBlockingQueue.
Clasa PriorityQueue moștenește Java Queue Interface și face parte din pachetul java.util.
Declarația generală a clasei PriorityQueue este dată mai jos:
public class PriorityQueue extends AbstractQueue implements SerializableDiagrama de mai jos prezintă ierarhia clasei pentru clasa PriorityQueue.
Complexitatea de timp a cozii prioritare
- Complexitatea în timp a cozii prioritare pentru metode de inserare (coadă) și ștergere (coadă) este O (log (n)).
- Coada prioritară are complexitate de timp liniară pentru eliminare, precum și conține metode.
- Metodele care recuperează elemente ale cozii de prioritate au o complexitate constantă a timpului.
Exemplu de coadă prioritară în Java
Programul de mai jos demonstrează o simplă PriorityQueue în Java. Creăm un obiect din clasa PriorityQueue, îi adăugăm valori și apoi afișăm conținutul cozii folosind Iterator.
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() + ' '); } } } Ieșire:
Java Priority Queue API Metode
Constructori:
| Prototipul constructorului | Descriere | |
|---|---|---|
| arunca o privire | E peek () | Returnează capul cozii fără a șterge elementul. |
| PriorityQueue () | Un constructor implicit care creează un obiect PriorityQueue cu capacitatea inițială de 1. | |
| PriorityQueue (Colecția c) | Creează un obiect PriorityQueue cu elemente inițiale dintr-o colecție dată c. | |
| PriorityQueue (int initialCapacity) | Creează un obiect PriorityQueue cu „initialCapacity” dată. Elementele sunt ordonate conform ordonării naturale. | |
| PriorityQueue (int initialCapacity, comparator comparator) | Creează un obiect PriorityQueue cu „initialCapacity” dată. Elementele sunt ordonate conform comparatorului dat. | |
| PriorityQueue (PriorityQueue c) | Creează un obiect PriorityQueue dintr-un alt obiect PriorityQueue dat de c. | |
| PriorityQueue (SortedSet c) | Creează un obiect PriorityQueue dintr-un SortedSet dat de c. |
Metode
| Metodă | Metoda prototip | Descriere |
|---|---|---|
| adăuga | add boolean (E e) | Adaugă elementul e la PriorityQueue. |
| clar | gol clar () | Șterge PriorityQueue ștergând toate elementele. |
| comparator | Comparator comparator () | Returnează un comparator personalizat utilizat pentru ordonarea elementelor din Coadă. |
| conține | boolean conține (Obiectul o) | Verifică dacă PriorityQueue conține elementul dat o. Returnează adevărat dacă da. |
| iterator | Iteratoriterator () | Metodă pentru a obține un iterator pentru PriorityQueue dat. |
| oferi | ofertă booleană (E e) | Inserați elementul dat e în PriorityQueue. |
| sondaj | Sondaj E () | Elimină și returnează capul cozii. Returnează nul dacă coada este goală. |
| elimina | eliminare booleană (Obiectul o) | Elimină o instanță a unui element dat o dacă este prezentă în coadă. |
| mărimea | int size () | Returnează dimensiunea sau numărul de elemente din această PriorityQueue. |
| toArray | Obiect () toArray () | Returnează o reprezentare matrice a PriorityQueue dat. |
| toArray | T () toArray (T () a) | Returnează o reprezentare a matricei pentru coada de prioritate dată cu același tip de rulare ca matricea specificată a. |
Implementare în Java
Să demonstrăm metodele de mai sus ale PriorityQueue utilizând un program 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 Ieșire:
care certificare de testare software este cea mai bună
Coadă prioritară în Java 8
Java 8 adaugă încă o metodă la clasa PriorityQueue, adică „spliterator ()”.
Detaliile acestei metode sunt prezentate mai jos.
Nume metodă: despicatoare
Metoda prototip: public final Spliterator spliterator ()
Descrierea metodei: Această metodă creează un spliterator peste elementele PriorityQueue. Acest spliterator se leagă târziu și eșuează rapid.
Comparator coadă prioritară
După cum sa menționat deja, elementele PriorityQueue sunt ordonate în mod natural. Dacă dorim să schimbăm comanda, atunci ar trebui să specificăm un comparator și să-l folosim în timpul creării obiectului PriorityQueue. PriorityQueue folosește apoi acest comparator pentru a-și ordona elementele.
Programul Java de mai jos demonstrează utilizarea comparatorului personalizat pentru ordonarea elementelor. În acest program, definim un nou comparator personalizat în interiorul căruia anulăm metoda „comparați”. Metoda de comparare este utilizată pentru a ordona elementele PriorityQueue în funcție de lungime.
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() + ' '); } } Ieșire:
Coadă de prioritate minimă în Java
Ordonarea naturală a cozii prioritare are cel mai mic sau cel mai mic element în capul cozii și astfel ordonarea este ascendentă. Aceasta se numește „coadă cu prioritate minimă”, cu ordinea crescătoare a elementelor.
Programul Java de mai jos prezintă implementarea cozii de prioritate minimă în 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 + ' '); } } } Ieșire:
Coadă de prioritate maximă în Java
În timp ce coada cu prioritate minimă are elemente în ordine crescătoare, coada cu prioritate maximă are elementele în ordine descrescătoare, adică capul cozii cu prioritate maximă va returna cel mai mare element din coadă.
Programul Java de mai jos demonstrează coada de prioritate maximă în 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 Ieșire:
După cum se arată în programul de mai sus, pentru a modifica ordinea naturală a elementelor din coada de prioritate, trebuie să definim un comparator personalizat.
cum să citiți fișierele .dat
întrebări frecvente
Q # 1) Care este coada prioritară în Java?
Răspuns: O coadă specială în care toate elementele cozii sunt ordonate conform unei comenzi naturale sau folosind un comparator personalizat se numește coadă prioritară. Nu respectă ordinea FIFO.
Q # 2) Cum setați o coadă cu prioritate maximă în Java?
Răspuns: Putem seta o coadă cu prioritate maximă în Java folosind un comparator personalizat, astfel încât capul cozii să returneze cel mai mare element din coadă.
Î. # 3) Coada prioritară permite duplicate Java?
Răspuns: Da. Coada prioritară permite duplicarea valorilor.
Q # 4) Este Java Priority coada max sau min?
Răspuns: În mod implicit, coada de prioritate în Java este coada de prioritate min cu comandă naturală. Pentru a-l face maxim, trebuie să folosim un comparator personalizat, astfel încât capul cozii să returneze cel mai mare element din coadă.
Q # 5) Este sortată o coadă prioritară?
Răspuns: În mod implicit, capul cozii este sortat, iar coada prioritară are cel mai mic element ca cap. Restul elementelor este comandat atunci când este necesar.
Concluzie
Aceasta completează tutorialul privind cozile prioritare în Java. Priority Queue implementează o interfață de coadă și este o coadă specială în care elementele sunt ordonate conform ordonării naturale. Nu respectă ordinea FIFO. Pentru a modifica ordinea naturală a cozii de prioritate, putem utiliza comparatorul personalizat.
Cozile prioritare sunt utilizate în principal pentru planificarea imprimantei, programarea sarcinilor procesorului, etc. Heap-ul (min sau max) este implementat și utilizând cozile prioritare.
=> Citiți seria Easy Training Java.
Lectură recomandată
- Structura de date a cozii prioritare în C ++ cu ilustrație
- Coadă prioritară în STL
- Coada Java - Metode de coadă, implementarea cozii cu exemple
- Structura de date a cozii circulare C ++: implementare și aplicații
- Coadă terminată dublă (Deque) în C ++ cu exemple
- Structura datelor în coadă în C ++ cu ilustrație
- Stive și cozi în STL
- Tutorial JAVA pentru începători: peste 100 de tutoriale video Java practice
