Java PriorityQueue

In deze zelfstudie leren we met behulp van voorbeelden over de klasse PriorityQueue van het Java-verzamelingsframework.

De PriorityQueue class biedt de functionaliteit van de heap-gegevensstructuur.

Het implementeert de wachtrij-interface.

In tegenstelling tot normale wachtrijen worden prioriteitswachtrij-elementen in gesorteerde volgorde opgehaald.

Stel dat we elementen in oplopende volgorde willen ophalen. In dit geval is de kop van de prioriteitswachtrij het kleinste element. Zodra dit element is opgehaald, zal het volgende kleinste element de kop van de wachtrij zijn.

Het is belangrijk op te merken dat de elementen van een prioriteitswachtrij mogelijk niet worden gesorteerd. Elementen worden echter altijd in gesorteerde volgorde opgehaald.

Prioriteitswachtrij maken

Om een ​​prioriteitswachtrij te maken, moeten we de java.util.PriorityQueue . importeren pakket. Zodra we het pakket hebben geïmporteerd, kunnen we als volgt een prioriteitswachtrij maken in Java.

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Hier hebben we een prioriteitswachtrij gemaakt zonder enige argumenten. In dit geval is de kop van de prioriteitswachtrij het kleinste element van de wachtrij. En elementen worden in oplopende volgorde uit de wachtrij verwijderd.

We kunnen de volgorde van elementen echter aanpassen met behulp van de Comparator koppel. We zullen daar later in deze tutorial meer over leren.

Methoden van PriorityQueue

De PriorityQueue class biedt de implementatie van alle methoden die aanwezig zijn in de Queue interface.

Elementen invoegen in PriorityQueue

• add() - Voegt het opgegeven element toe aan de wachtrij. Als de wachtrij vol is, wordt er een uitzondering gegenereerd.
• offer() - Voegt het opgegeven element toe aan de wachtrij. Als de wachtrij vol is, wordt false . geretourneerd .

Bijvoorbeeld,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        // Using the add() method
        numbers.add(4);
        numbers.add(2);
        System.out.println("PriorityQueue: " + numbers);

        // Using the offer() method
        numbers.offer(1);
        System.out.println("Updated PriorityQueue: " + numbers);
    }
}

Uitvoer

PriorityQueue: [2, 4]
Updated PriorityQueue: [1, 4, 2]

Hier hebben we een prioriteitswachtrij gemaakt met de naam nummers . We hebben 4 en 2 ingevoegd in de wachtrij.

Hoewel 4 vóór 2 wordt ingevoegd, is de kop van de wachtrij 2. Dit komt omdat de kop van de prioriteitswachtrij het kleinste element van de wachtrij is.

We hebben dan 1 ingevoegd in de wachtrij. De wachtrij is nu herschikt om het kleinste element 1 aan de kop van de wachtrij op te slaan.

Toegang PriorityQueue-elementen

Om toegang te krijgen tot elementen uit een prioriteitswachtrij, kunnen we de peek() . gebruiken methode. Deze methode retourneert de kop van de wachtrij. Bijvoorbeeld,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the peek() method
        int number = numbers.peek();
        System.out.println("Accessed Element: " + number);
    }
}

Uitvoer

PriorityQueue: [1, 4, 2]
Accessed Element: 1

PriorityQueue-elementen verwijderen

• remove() - verwijdert het opgegeven element uit de wachtrij
• poll() - keert terug en verwijdert de kop van de wachtrij

Bijvoorbeeld,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the remove() method
        boolean result = numbers.remove(2);
        System.out.println("Is the element 2 removed? " + result);

        // Using the poll() method
        int number = numbers.poll();
        System.out.println("Removed Element Using poll(): " + number);
    }
}

Uitvoer

PriorityQueue: [1, 4, 2]
Is the element 2 removed? true
Removed Element Using poll(): 1

Itereren over een PriorityQueue

Om de elementen van een prioriteitswachtrij te herhalen, kunnen we de iterator() . gebruiken methode. Om deze methode te gebruiken, moeten we de java.util.Iterator . importeren pakket. Bijvoorbeeld,

import java.util.PriorityQueue;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.print("PriorityQueue using iterator(): ");

        //Using the iterator() method
        Iterator<Integer> iterate = numbers.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

Uitvoer

PriorityQueue using iterator(): 1, 4, 2,

Andere PriorityQueue-methoden

PriorityQueue Comparator

In alle bovenstaande voorbeelden worden prioriteitswachtrij-elementen in de natuurlijke volgorde (oplopende volgorde) opgehaald. We kunnen deze volgorde echter aanpassen.

Hiervoor moeten we onze eigen comparatorklasse maken die de Comparator . implementeert koppel. Bijvoorbeeld,

import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>(new CustomComparator());
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        numbers.add(3);
        System.out.print("PriorityQueue: " + numbers);
    }
}

class CustomComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer number1, Integer number2) {
        int value =  number1.compareTo(number2);
        // elements are sorted in reverse order
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}

Uitvoer

PriorityQueue: [4, 3, 1, 2]

In het bovenstaande voorbeeld hebben we een prioriteitswachtrij gemaakt die CustomComparator . doorgeeft class als argument.

De CustomComparator class implementeert de Comparator interface.

We overschrijven dan de compare() methode. De methode zorgt er nu voor dat de kop van het element het grootste getal is.

Ga voor meer informatie over de comparator naar Java Comparator.