java priority queue tutorial implementation examples
Denne veiledningen forklarer Java Priority Queue og relaterte konsepter som Comparator, Min og Max Priority Queue sammen med implementeringen med eksempler:
Prioritetskø datastruktur er en spesiell kø der elementene er tilstede ikke i henhold til FIFO-ordren, men i henhold til de naturlige elementene eller en hvilken som helst tilpasset komparator som brukes under køopprettelse.
=> Ta en titt på Java Beginners Guide her.
Hva du vil lære:
Prioritetskø i Java
I Priority Queue har forsiden av køen de minste elementene i henhold til den naturlige rekkefølgen, og den bakre er pekt mot det største elementet i køen.
Et eksempel Prioritetskø bestående av tall er vist nedenfor.
c ++ kompilator for formørkelse
Dermed når et element fjernes fra prioritetskøen vist ovenfor, vil det være det minste elementet.
På samme måte, for en alfabetisk prioritetskø, vil ASCII-verdier bli vurdert, og køelementene vil bli ordnet i henhold til ASCII-verdiene.
Nedenfor er noen av de viktigste egenskapene til PriorityQueue:
- PriorityQueue er en ubundet kø.
- PriorityQueue tillater ikke nullverdier.
- For ikke-sammenlignbare objekter kan vi ikke opprette en prioritetskø.
- PriorityQueue arver fra klassene som AbstractQueue, AbstractCollection, Collection og Object.
- Hodet eller forsiden av køen inneholder det minste elementet i henhold til den naturlige bestillingen.
- Prioriteringskø-implementering er ikke trådsikker. Dermed hvis vi ønsker synkronisert tilgang, bør vi bruke PriorityBlockingQueue.
PriorityQueue-klassen arver Java Queue Interface og er en del av pakken java.util.
Den generelle erklæringen til PriorityQueue-klassen er gitt nedenfor:
public class PriorityQueue extends AbstractQueue implements SerializableDiagrammet nedenfor viser klassehierarkiet for PriorityQueue-klassen.
Tidskompleksitet av prioritetskø
- Tidskompleksiteten til Priority Queue for insertion (enqueue) og sletting (dequeue) metoder er O (log (n)).
- Prioritetskø har lineær tidskompleksitet for fjerning og inneholder metoder.
- Metodene som henter elementer i Priority Queue har konstant tidskompleksitet.
Prioritetskø Eksempel i Java
Programmet nedenfor viser en enkel PriorityQueue i Java. Vi oppretter et objekt av PriorityQueue-klassen, legger til verdier i det, og viser deretter innholdet i køen ved hjelp av 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() + ' '); } } } Produksjon:
Java Priority Queue API Methods
Konstruktører:
| Konstruktørprototype | Beskrivelse | |
|---|---|---|
| kikke | E titt () | Returnerer køhodet uten å slette elementet. |
| PriorityQueue () | En standardkonstruktør som oppretter et PriorityQueue-objekt med startkapasitet som 1. | |
| PriorityQueue (samling c) | Oppretter et PriorityQueue-objekt med innledende elementer fra gitt samling c. | |
| PriorityQueue (int initialCapacity) | Oppretter et PriorityQueue-objekt med den gitte 'initialCapacity'. Elementer bestilles i henhold til naturlig bestilling. | |
| PriorityQueue (int initialCapacity, Comparator comparator) | Oppretter et PriorityQueue-objekt med den gitte 'initialCapacity'. Elementene er ordnet i henhold til den gitte komparatoren. | |
| PriorityQueue (PriorityQueue c) | Oppretter et PriorityQueue-objekt fra et annet PriorityQueue-objekt gitt av c. | |
| PriorityQueue (SortedSet c) | Oppretter et PriorityQueue-objekt fra et SortedSet gitt av c. |
Metoder
| Metode | Metode Prototype | Beskrivelse |
|---|---|---|
| Legg til | boolsk tilsetning (E e) | Legger til element e i PriorityQueue. |
| klar | ugyldig klar () | Fjerner PriorityQueue ved å slette alle elementene. |
| komparator | Comparatorcomparator () | Returnerer en tilpasset komparator som brukes for bestilling av elementer i køen. |
| inneholder | boolsk inneholder (Objekt o) | Sjekker om PriorityQueue inneholder det gitte elementet o. Returnerer sant hvis ja. |
| iterator | Iteratoriterator () | Metode for å få en iterator for den gitte PriorityQueue. |
| by på | boolsk tilbud (E e) | Sett inn gitt element e i PriorityQueue. |
| avstemming | E-avstemning () | Fjerner og returnerer køhodet. Returnerer null hvis køen er tom. |
| ta vekk | boolsk fjerning (Objekt o) | Fjerner en forekomst av et gitt element o hvis det er til stede i køen. |
| størrelse | int størrelse () | Returnerer størrelsen eller antallet elementer i denne PriorityQueue. |
| toArray | Objekt () toArray () | Returnerer en matrixrepresentasjon av den gitte PriorityQueue. |
| toArray | T () toArray (T () a) | Returnerer en matrixrepresentasjon for den gitte prioritetskøen med samme kjøretidstype som den angitte matrisen a. |
Implementering i Java
La oss demonstrere metodene ovenfor i PriorityQueue ved hjelp av et Java-program.
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 Produksjon:
gjør char til int c ++
Prioritetskø i Java 8
Java 8 legger til en metode til PriorityQueue-klassen, dvs. 'spliterator ()'.
Detaljer om denne metoden er gitt nedenfor.
Metodenavn: splitter
Metodeprototype: offentlig finale Spliterator spliterator ()
Metode Beskrivelse: Denne metoden oppretter en spliterator over PriorityQueue-elementene. Denne spliteratoren er senbindende og mislykkes rask.
Prioritetskø-komparator
Som allerede nevnt er PriorityQueue-elementer naturlig bestilt. Hvis vi vil endre rekkefølgen, bør vi spesifisere en komparator og bruke den under opprettelsen av PriorityQueue-objektet. PriorityQueue bruker deretter denne komparatoren for å bestille elementene.
Java-programmet nedenfor viser bruken av tilpasset komparator for bestilling av elementer. I dette programmet definerer vi en ny tilpasset komparator der vi overstyrer 'sammenligne'-metoden. Sammenligningsmetoden brukes til å bestille elementene i PriorityQueue i henhold til lengden.
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() + ' '); } } Produksjon:
Min prioritetskø i Java
Den naturlige bestillingen av Priority Queue har det minste eller minste elementet i toppen av køen, og bestillingen stiger dermed. Dette kalles 'Min prioritetskø' med stigende rekkefølge av elementer.
Java-programmet nedenfor viser implementeringen av Min Priority Queue i 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 + ' '); } } } Produksjon:
Maks prioritetskø i Java
Mens min prioritetskø har elementer i stigende rekkefølge, har maksimal prioritetskø elementene i fallende rekkefølge, dvs. hodet til Maks prioritetskø vil returnere det største elementet i køen.
Java-programmet nedenfor viser Max Priority Queue i 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 Produksjon:
Som vist i programmet ovenfor, må vi definere en tilpasset komparator for å endre den naturlige rekkefølgen av elementer i prioritetskøen.
ofte stilte spørsmål
Q # 1) Hva er Priority-køen i Java?
Svar: En spesiell kø der alle elementene i køen er bestilt i henhold til naturlig bestilling eller ved bruk av en tilpasset komparator, kalles Priority-køen. Den følger ikke FIFO-ordren.
Spørsmål 2) Hvordan setter du en maks prioritets kø i Java?
Svar: Vi kan angi en maksimal prioritetskø i Java ved hjelp av en tilpasset komparator slik at køhodet vil returnere det største elementet i køen.
Q # 3) Tillater Priority-køen dupliserte Java?
Svar: Ja. Prioritetskø tillater dupliserte verdier.
Q # 4) Er Java Priority-kø maks eller min?
Svar: Som standard er prioritetskøen i Java min Prioritetskø med naturlig bestilling. For å gjøre det maksimalt må vi bruke en tilpasset komparator slik at køhodet returnerer det største elementet i køen.
dobbeltkoblet listeklasse c ++
Q # 5) Er en prioritetskø sortert?
Svar: Som standard er køhodet sortert, og Prioritetskøen har det minste elementet som hode. Resten av elementene bestilles når det er nødvendig.
Konklusjon
Dette fullfører opplæringen om prioritetskøer i Java. Priority Queue implementerer et køgrensesnitt og er en spesiell kø der elementer bestilles i henhold til naturlig bestilling. Den følger ikke FIFO-ordren. For å endre den naturlige rekkefølgen på prioritetskøen, kan vi bruke den tilpassede komparatoren.
Prioritetskøer brukes hovedsakelig til skriverplanlegging, CPU-oppgaveplanlegging osv. Haugen (min eller maks) implementeres også ved hjelp av Priority Queues.
=> Les gjennom Easy Java Training Series.
Anbefalt lesing
- Prioritert kødatastruktur i C ++ med illustrasjon
- Prioritetskø I STL
- Java kø - kømetoder, køimplementering med eksempler
- C ++ Circular Queue Data Structure: Implementation & Applications
- Dobbelt slutt kø (Deque) i C ++ med eksempler
- Kødatastruktur i C ++ med illustrasjon
- Stabler og køer i STL
- JAVA-opplæring for nybegynnere: 100+ praktiske Java-videoveiledninger
