java priority queue tutorial implementation examples
In deze zelfstudie worden de Java-prioriteitswachtrij en gerelateerde concepten zoals Comparator, Min en Max Priority-wachtrij uitgelegd, samen met de implementatie ervan met voorbeelden:
Priority Queue-gegevensstructuur is een speciale wachtrij waarin de elementen niet per FIFO-volgorde aanwezig zijn, maar volgens de natuurlijke elementen of een aangepaste vergelijker die wordt gebruikt tijdens het maken van een wachtrij.
Bekijk hier de Java-beginnershandleiding.
Wat je leert:
Prioriteitswachtrij in Java
In Priority Queue heeft de voorkant van de wachtrij de minste elementen volgens de natuurlijke volgorde en wordt de achterkant naar het grootste element in de wachtrij verwezen.
Hieronder ziet u een voorbeeld van een prioriteitswachtrij die uit getallen bestaat.
hoe je privémethoden test met behulp van mockito
Dus wanneer een element wordt verwijderd uit de hierboven getoonde prioriteitswachtrij, dan is dit het minste element.
Evenzo worden voor een alfabetische prioriteitswachtrij ASCII-waarden in overweging genomen en worden de wachtrij-elementen gerangschikt volgens de ASCII-waarden.
Hieronder staan enkele van de belangrijkste kenmerken van de PriorityQueue:
- PriorityQueue is een ongebonden wachtrij.
- PriorityQueue staat geen null-waarden toe.
- Voor niet-vergelijkbare objecten kunnen we geen prioriteitswachtrij maken.
- PriorityQueue erft van de klassen zoals AbstractQueue, AbstractCollection, Collection en Object.
- Het hoofd of de voorkant van de wachtrij bevat het minste element volgens de natuurlijke volgorde.
- Priority Queue-implementatie is niet thread-safe. Dus als we gesynchroniseerde toegang wensen, moeten we de PriorityBlockingQueue gebruiken.
De PriorityQueue-klasse neemt de Java Queue Interface over en maakt deel uit van het pakket java.util.
De algemene verklaring van de klasse PriorityQueue wordt hieronder gegeven:
Het onderstaande diagram toont de klassehiërarchie voor de klasse PriorityQueue.
Tijdscomplexiteit van prioriteitswachtrij
- De tijdcomplexiteit van de prioriteitswachtrij voor methoden voor invoegen (in de wachtrij plaatsen) en verwijderen (uit de wachtrij halen) is O (log (n)).
- Priority Queue heeft een lineaire tijdcomplexiteit voor verwijderen en bevat ook methoden.
- De methoden die elementen van de prioriteitswachtrij ophalen, hebben een constante tijdcomplexiteit.
Voorbeeld van een prioriteitswachtrij in Java
Het onderstaande programma demonstreert een eenvoudige PriorityQueue in Java. We maken een object van de PriorityQueue-klasse, voegen er waarden aan toe en geven vervolgens de inhoud van de wachtrij weer met Iterator.
Uitgang:
Java Priority Queue API-methoden
Constructeurs:
| Constructor-prototype | Omschrijving | |
|---|---|---|
| kijkje | E peek () | Geeft de kop van de wachtrij terug zonder het element te verwijderen. |
| Prioriteits-rij () | Een standaardconstructor die een PriorityQueue-object maakt met een initiële capaciteit van 1. | |
| PriorityQueue (Collectie c) | Maakt een PriorityQueue-object met initiële elementen uit een bepaalde verzameling c. | |
| PriorityQueue (int initialCapacity) | Maakt een PriorityQueue-object met de gegeven ‘initialCapacity’. Elementen worden gerangschikt volgens natuurlijke volgorde. | |
| PriorityQueue (int initialCapacity, Comparator-comparator) | Maakt een PriorityQueue-object met de gegeven ‘initialCapacity’. De elementen zijn gerangschikt volgens de opgegeven vergelijker. | |
| PriorityQueue (PriorityQueue c) | Maakt een PriorityQueue-object van een ander PriorityQueue-object gegeven door c. | |
| PriorityQueue (SortedSet c) | Maakt een PriorityQueue-object van een SortedSet gegeven door c. |
Methoden
| Methode | Methode Prototype | Omschrijving |
|---|---|---|
| toevoegen | boolean add (E e) | Voegt element e toe aan de PriorityQueue. |
| Doorzichtig | leegte duidelijk () | Wist de PriorityQueue door alle elementen te verwijderen. |
| comparator | Vergelijkervergelijker () | Retourneert een aangepaste vergelijker die wordt gebruikt voor de volgorde van elementen in de wachtrij. |
| bevat | boolean bevat (Object o) | Controleert of de PriorityQueue het gegeven element o bevat. Retourneert true indien ja. |
| iterator | Iteratoriterator () | Methode om een iterator te krijgen voor de opgegeven PriorityQueue. |
| aanbod | booleaanse aanbieding (E e) | Voeg het gegeven element e in de PriorityQueue in. |
| poll | E poll () | Verwijdert en geeft de kop van de wachtrij terug. Retourneert null als de wachtrij leeg is. |
| verwijderen | boolean remove (Object o) | Verwijdert een instantie van een bepaald element o als het in de wachtrij staat. |
| grootte | int maat () | Retourneert de grootte of het aantal elementen in deze PriorityQueue. |
| toArray | Object () toArray () | Retourneert een matrixweergave van de opgegeven PriorityQueue. |
| toArray | T () toArray (T () a) | Retourneert een matrixweergave voor de opgegeven prioriteitswachtrij met hetzelfde runtime-type als de opgegeven matrix a. |
Implementatie in Java
Laten we de bovenstaande methoden van PriorityQueue demonstreren met behulp van een Java-programma.
Uitgang:
hoe je een project maakt in eclips
Prioriteitswachtrij in Java 8
Java 8 voegt nog een methode toe aan de PriorityQueue-klasse, namelijk ‘spliterator ()’.
De details van deze methode worden hieronder gegeven.
Methode naam: splitser
Methode Prototype: openbare finale Spliterator spliterator ()
Methode Beschrijving: Deze methode maakt een spliterator over de PriorityQueue-elementen. Deze spliterator is laat bindend en faalt snel.
Prioriteitswachtrijvergelijker
Zoals eerder vermeld, zijn PriorityQueue-elementen natuurlijk geordend. Als we de volgorde willen wijzigen, moeten we een comparator specificeren en deze gebruiken tijdens het maken van het PriorityQueue-object. De PriorityQueue gebruikt deze comparator vervolgens om de elementen te ordenen.
Het onderstaande Java-programma demonstreert het gebruik van een aangepaste comparator voor het bestellen van elementen. In dit programma definiëren we een nieuwe aangepaste comparator waarin we de ‘vergelijk’ -methode overschrijven. De vergelijkingsmethode wordt gebruikt om de elementen van de PriorityQueue te ordenen op basis van de lengte.
Uitgang:
Min. Prioriteitswachtrij in Java
De natuurlijke volgorde van Priority Queue heeft het minste of kleinste element bovenaan de wachtrij en dus stijgt de volgorde. Dit wordt de 'Min prioriteit wachtrij' genoemd met oplopende volgorde van elementen.
Het onderstaande Java-programma toont de implementatie van de Min Priority Queue in Java.
Uitgang:
java versus c ++ verschillen
Max. Prioriteitswachtrij in Java
Terwijl de wachtrij met minimale prioriteit elementen in oplopende volgorde heeft, heeft de wachtrij met maximale prioriteit de elementen in aflopende volgorde, d.w.z. het hoofd van de wachtrij met maximale prioriteit zal het grootste element in de wachtrij retourneren.
Het onderstaande Java-programma demonstreert de Max Priority Queue in Java.
Uitgang:
Zoals getoond in het bovenstaande programma, moeten we een aangepaste comparator definiëren om de natuurlijke volgorde van elementen in de prioriteitswachtrij te wijzigen.
Veel Gestelde Vragen
V # 1) Wat is de prioriteitswachtrij in Java?
Antwoord: Een speciale wachtrij waarin alle elementen van de wachtrij zijn gerangschikt volgens natuurlijke volgorde of met behulp van een aangepaste vergelijker, wordt de Priority-wachtrij genoemd. Het volgt niet de FIFO-volgorde.
Vraag 2) Hoe stel je een Max Priority-wachtrij in Java in?
Antwoord: We kunnen een Max Priority-wachtrij in Java instellen met behulp van een aangepaste comparator, zodat de kop van de wachtrij het grootste element in de wachtrij retourneert.
V # 3) Staat de prioriteitswachtrij duplicaten van Java toe?
Antwoord: Ja. Priority Queue staat dubbele waarden toe.
V # 4) Is de Java-prioriteitswachtrij max of min?
Antwoord: Standaard is de prioriteitswachtrij in Java min Priority-wachtrij met natuurlijke volgorde. Om het maximaal te maken, moeten we een aangepaste comparator gebruiken, zodat het hoofd van de wachtrij het grootste element in de wachtrij retourneert.
V # 5) Is een prioriteitswachtrij gesorteerd?
Antwoord: Standaard is de kop van de wachtrij gesorteerd en heeft de prioriteitswachtrij het minste element als kop. De rest van de elementen wordt indien nodig besteld.
Gevolgtrekking
Hiermee is de tutorial over prioriteitswachtrijen in Java voltooid. Priority Queue implementeert een wachtrij-interface en is een speciale wachtrij waarin elementen worden geordend volgens de natuurlijke volgorde. Het volgt niet de FIFO-volgorde. Om de natuurlijke volgorde van de prioriteitswachtrij te wijzigen, kunnen we de aangepaste comparator gebruiken.
Prioriteitswachtrijen worden voornamelijk gebruikt voor printerplanning, CPU-taakplanning, enz. De heap (min of max) wordt ook geïmplementeerd met behulp van prioriteitswachtrijen.
Lees de Easy Java Training Series door.
Aanbevolen literatuur
- Prioritaire wachtrijgegevensstructuur in C ++ met illustratie
- Prioriteitswachtrij in STL
- Java-wachtrij - wachtrijmethoden, wachtrij-implementatie met voorbeelden
- C ++ Circular Queue-gegevensstructuur: implementatie en toepassingen
- Double Ended Queue (Deque) in C ++ met voorbeelden
- Wachtrijgegevensstructuur in C ++ met illustratie
- Stapels en wachtrijen in STL
- JAVA-zelfstudie voor beginners: 100+ praktische Java-videotutorials