Prioriteitswachtrij Java

Af en toe moeten we items van een wachtrij verwerken in een specifieke volgorde. Een prioriteitswachtrij is een gegevensstructuur die deze taak uitvoert. De Java-prioriteitswachtrij verschilt van een “normale” wachtrij. In plaats van “First-In-First-Out” haalt het items op in volgorde van hun prioriteit.

Prioriteitswachtrij Java

De klasse java.util.PriorityQueue biedt ons een implementatie van dit gegevenstype door intern een prioriteitsheap-implementatie te gebruiken. Java PriorityQueue is een onbegrensde wachtrij. Het werd geïntroduceerd in Java 1.5 en verbeterd in de release van Java SE 8. PriorityQueue is intern geïmplementeerd met behulp van de gegevensstructuur “Priority Heap”. Hier is de hiërarchie van de PriorityQueue-klasse: Prioriteitswachtrijklassendiagram:

Java PriorityQueue-constructeurs

1. PriorityQueue() – Maakt een PriorityQueue aan met de standaard initiële capaciteit, d.w.z. 11
2. PriorityQueue(Collection c) – Maakt een PriorityQueue aan met de elementen in de gespecificeerde verzameling
3. PriorityQueue(int initialCapacity) – Maakt een PriorityQueue met de gespecificeerde initiële capaciteit
4. PriorityQueue(int initialCapacity, Comparator comparator) – Maakt een PriorityQueue met de opgegeven initiële capaciteit en de volgorde van de elementen wordt bepaald door de gespecificeerde comparator
5. PriorityQueue(PriorityQueue c) – Maakt een PriorityQueue met de elementen in de gespecificeerde prioriteitswachtrij
6. PriorityQueue(SortedSet c) – Maakt een PriorityQueue met de elementen in de gespecificeerde gesorteerde set

De elementen van de prioriteitswachtrij worden geordend volgens hun natuurlijke volgorde, tenzij we een Comparator opgeven bij het maken ervan. De elementen worden standaard in oplopende volgorde geordend, dus het hoofd van de wachtrij is het element waarvan de prioriteit het laagst is. Als er twee elementen zijn die tegelijkertijd in aanmerking komen om het hoofd te worden, worden dergelijke gelijkspel willekeurig verbroken.

Java PriorityQueue Voorbeeld

Laten we een PriorityQueue maken met verschillende taken:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

Dit maakt een PriorityQueue van taken, die zal worden geordend volgens de natuurlijke volgorde van String. Laten we nog een PriorityQueue maken die de taken in omgekeerde volgorde van de natuurlijke volgorde ordent. We moeten dus een Comparator doorgeven:

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java PriorityQueue Methoden

Laten we nu eens kijken naar alle beschikbare methoden voor PriorityQueue en deze gebruiken:

1. Boolean add(E e) – Deze methode voegt het gespecificeerde element toe aan de wachtrij. We hebben al 5 taken aan onze wachtrij toegevoegd met behulp van deze methode.

2. Comparator comparator() – Deze methode retourneert de Comparator die wordt gebruikt om de elementen in deze wachtrij te ordenen. Het retourneert null als er geen comparator is gespecificeerd en de wachtrij wordt gesorteerd volgens de natuurlijke volgorde van de elementen. Dus, als we dit doen:

   System.out.println(tasks.comparator());
   System.out.println(reverseTasks.comparator());
   

   Het resultaat zal zijn:

   null
   java.util.Collections$ReverseComparator@15db9742
   

3. boolean bevat(Object o) – Geeft true terug als de wachtrij het gespecificeerde element bevat. Laten we controleren of “taak3” behoort tot de prioriteitswachtrij taken:

   System.out.println(taken.bevat("taak3"));
   

   Dit geeft uit:

   true
   

4. boolean aanbieden(E e) – Net als de add()-methode voegt deze methode ook een element toe aan de wachtrij. De aanbieden() en add()-methoden zijn eigenlijk een beetje verschillend voor capaciteitsbeperkte wachtrijen, maar in het geval van PriorityQueue zijn ze hetzelfde. In tegenstelling tot add() gooit aanbieden() geen uitzondering, zelfs als het niet lukt om het element aan de wachtrij toe te voegen.

5. E bekijken() – Haalt het hoofd van deze wachtrij op, of geeft null terug als deze wachtrij leeg is. Met andere woorden, het geeft het element met de hoogste prioriteit terug. Dus de volgende code:

   System.out.println(taken.bekijken());
   System.out.println(omgekeerdeTaken.bekijken());
   

   Geeft ons:

   taak1
   taak5
   

6. E poll() – Deze methode haalt ook het hoofd van de wachtrij op (het element met de hoogste prioriteit), of geeft null terug als de wachtrij leeg is. Maar in tegenstelling tot peek(), verwijdert het ook het element. Dus, als we poll() aanroepen:

   System.out.println("Poll op taken: "+taken.poll());
   System.out.println("Poll op reverseTaken: "+reverseTaken.poll());
   

   En dan peek:

   System.out.println("Peek op taken: "+taken.peek());
   System.out.println("Peek op reverseTaken: "+reverseTaken.peek());
   

   We krijgen de volgende uitvoer:

   Poll op taken: taak1
   Poll op reverseTaken: taak5
   Peek op taken: taak2
   Peek op reverseTaken: taak4
   

7. int size() – Geeft het aantal elementen in de wachtrij terug.

8. boolean remove(Object o) – Verwijdert het opgegeven element uit de wachtrij, indien aanwezig. Als twee identieke elementen aanwezig zijn, wordt er slechts één van verwijderd.

9. Object[] toArray() – Geeft een array terug met alle elementen in de wachtrij.

10. T[] toArray(T[] a) – Geeft een array terug die alle elementen in de wachtrij bevat, en het type van de teruggegeven array is dat van de gespecificeerde array.

11. Iterator iterator() – Geeft een iterator terug voor de wachtrij.

12. void clear() – Verwijdert alle elementen uit de wachtrij.

Apart from these, the PriorityQueue also inherits the methods from the Collection and Object classes.

Java PriorityQueue Time Complexity

1. Voor enqueuen en dequeuen methoden, is de tijdcomplexiteit O(log(n))
2. Voor de remove(Object) en contains(Object) methoden, is de tijdcomplexiteit lineair
3. Voor de opvraagmethoden heeft het een constante tijdcomplexiteit

Deze implementatie van prioriteitswachtrij is niet thread-safe. Dus, als we gesynchroniseerde toegang nodig hebben, moeten we PriorityBlockingQueue gebruiken. Referentie: API-documentatie