Java Priority Queue: nu este o coadă clasică

În acest articol aflăm o coadă prioritară, clasa Java, care implementează interfața Queue. Ce știe un programator despre interfața obișnuită de coadă? În primul rând, această interfață se bazează pe principiul FIFO sau „primul intrat, primul ieșit”. Asta amintește de o coadă obișnuită în sensul său comun. Vrei să iei cafea de la McDrive? Dacă mașina ta este prima lângă fereastră, vei primi cafeaua înaintea șoferului care urmează.

Declarație de interfață de coadă

public interface Queue<E> extends Collection<E>

Ce este o coadă prioritară

Ce este o coadă prioritară? In primul rand este o clasa care implementeaza interfata Queue in cazul introducerii unui element din spate si scoaterii unui element din cap. Cu toate acestea, nu este o coadă obișnuită în interior. Ordinea elementelor din coada de prioritate Java depinde de prioritatea elementelor. Elementul cu cea mai mare prioritate va fi mutat în capul cozii. Dacă ștergeți (serviți) elementul cel mai bine clasat, al doilea se duce la cap să-și ia cafeaua. Cum se determină prioritatea? Conform documentatiei, elementele cozii de prioritate sunt ordonate dupa ordonarea lor fireasca, sau printr-un Comparator pus la dispozitie in momentul construirii cozii, in functie de constructorul folosit. O coadă de prioritate bazată pe o grămadă min de prioritate. Aceasta înseamnă că, în cazul elementelor de coadă de numere, primul element al cozii va fi minimul acestor numere. Destul de des, după ce citesc această definiție, studenții începători încep să creadă că coada de prioritate este sortată într-un sens liniar. Adică, dacă, să zicem, folosim o coadă ale cărei elemente sunt numere naturale, atunci primul element va fi cel mai mic, iar ultimul - cel mai mare. Acest lucru nu este în întregime adevărat. Pentru a înțelege cum funcționează de fapt coada de prioritate și ce oferă, trebuie să vă dați seama cum funcționează heap-ul. Luăm în considerare structura internă a cozii de prioritate folosind un exemplu puțin mai târziu. Acum să ne oprim asupra atributelor sale externe. atunci primul element va fi cel mai mic, iar ultimul - cel mai mare. Acest lucru nu este în întregime adevărat. Pentru a înțelege cum funcționează de fapt coada de prioritate și ce oferă, trebuie să vă dați seama cum funcționează heap-ul. Luăm în considerare structura internă a cozii de prioritate folosind un exemplu puțin mai târziu. Acum să ne oprim asupra atributelor sale externe. atunci primul element va fi cel mai mic, iar ultimul - cel mai mare. Acest lucru nu este în întregime adevărat. Pentru a înțelege cum funcționează de fapt coada de prioritate și ce oferă, trebuie să vă dați seama cum funcționează heap-ul. Luăm în considerare structura internă a cozii de prioritate folosind un exemplu puțin mai târziu. Acum să ne oprim asupra atributelor sale externe.

Constructorii clasei PriorityQueue și declarația

Clasa PriorityQueue oferă 6 moduri diferite de a construi o coadă de prioritate în Java.

• PriorityQueue() - coadă goală cu capacitatea inițială implicită (11) care își ordonează elementele în funcție de ordonarea lor naturală.
• PriorityQueue(Colecția c) - coadă goală care conține elementele din colecția specificată.
• PriorityQueue(int initialCapacity) - coada goala cu capacitatea initiala specificata care isi ordoneaza elementele in functie de ordonarea lor naturala.
• PriorityQueue(int initialCapacity, Comparator comparator) - coadă goală cu capacitatea inițială specificată care își ordonează elementele conform comparatorului specificat.
• PriorityQueue(PriorityQueue c) - coadă goală care conține elementele din coada de prioritate specificată.
• PriorityQueue(SortedSet c) - coadă goală care conține elementele din setul sortat specificat.

Coada prioritară în Java este declarată în felul următor:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Se creează PriorityQueue

Să creăm o coadă prioritară de numere întregi. Implementarea cozii prioritare, cod Java:

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

Am creat o coadă de prioritate fără argumente. În acest caz, capul cozii de prioritate este numărul minim al cozii. Dacă îndepărtați capul, următorul cel mai mic element va ocupa acest loc. Astfel, puteți elimina elemente din coadă în ordine crescătoare. Dacă este necesar, puteți schimba principiul comenzii folosind interfața Comparator.

Metode Java PriorityQueue

Clasa Java PriorityQueue are metode importante pentru a adăuga, elimina și verifica elemente.

Inserați elemente în coada de prioritate

• boolean add(object) inserează elementul specificat în coada de prioritate. Returnează adevărat în caz de succes. Dacă coada este plină, metoda aruncă o excepție.
• oferta booleană (obiect) inserează elementul specificat în această coadă de prioritate. Dacă coada este plină, metoda returnează false.

Puteți utiliza ambele operațiuni de adăugare, nu există diferențe pentru cazurile majoritare. Iată un mic exemplu de inițiere și adăugare de elemente în coada de prioritate.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

Ieșirea este:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

Ordinea elementelor pare a fi ciudată, o vom explica mai târziu.

Preluarea și eliminarea elementelor din coada de prioritate

• boolean remove(obiect) elimină o singură instanță a elementului specificat din această coadă, dacă este prezentă.
• Object poll() preia și elimină capul acestei cozi. Returnează null dacă coada este goală.
• void clear() elimină toate elementele din coada de prioritate.
• Object element() preia capul acestei cozi fără a-l elimina. Aruncă NoSuchElementException dacă coada este goală.
• Object peek() preia capul cozii fără a-l elimina. Returnează null dacă coada este goală.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Ieșire:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

După cum puteți vedea, încercarea de a tipări capul cozii goale folosind metoda element() duce la NoSuchElementexception .

Comparator PriorityQueue

• Comparator comparator() returnează comparatorul care a folosit pentru a ordona elementele din coadă. Returnează null dacă coada este sortată în funcție de ordinea naturală a elementelor sale.

Coada de prioritate Java, exemplu cu comparator

Am folosit ordinea naturală (crescătoare) în exemplele de cod de mai sus, dar uneori ar trebui să o schimbăm. Iată un exemplu de coadă de prioritate Java, în care creăm propria noastră clasă internă de comparare care implementează interfața Comparator. Comparatorul nostru va sorta elementele de la cel mai mare la cel mai mic.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Ieșirea:

the head of Queue = 5
5
4
3
2
1

Capul de coadă acum nu este elementul minim, ci maxim, iar ordinea a fost schimbată în inversă.

Iterarea peste PriorityQueue folosind iteratorul

ProrityQueue este o parte a cadrului Collection și implementează interfața Iterable<> . Pentru a itera elementele unei cozi de prioritate, puteți utiliza metoda iterator() . Iată un exemplu:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Ieșire:

1 2 4 5 3 

Mai multe metode PriorityQueue

• boolean contains(Object o) returnează adevărat dacă coada conține elementul o.
• int size() returnează numărul de elemente din această coadă.
• Object[] toArray() returnează o matrice care conține toate elementele din această coadă.

Iată un exemplu:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Ieșire:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

Definiția PriorityQueue Java 8

Dacă deschideți documentația priorityqueue java 8, veți găsi acolo următoarea definiție: O coadă de prioritate nelimitată bazată pe un heap de prioritate. Elementele cozii de prioritate sunt ordonate în funcție de ordonarea lor naturală, sau de un Comparator furnizat în momentul construirii cozii, în funcție de constructorul utilizat. O coadă cu prioritate nu permite elemente nule. O coadă de prioritate care se bazează pe ordonarea naturală nu permite, de asemenea, inserarea de obiecte necomparabile (în acest fel poate duce la ClassCastException). Heap este un cuvânt foarte important aici. Acesta explică proprietățile ordonării elementelor din Coada prioritară.

Principiul funcționării PriorityQueue: Binary Heap

Să începem cu un exemplu. Să creăm două obiecte care implementează interfața Queue. Unul dintre ele LinkedList, al doilea — PriorityQueue. Ambele au 5 elemente de Integer (1,2,3,4 și 5) și începem să punem elementele în cozile noastre de la cel mai mare la cel mai mic. Deci, primul vine 5, apoi 4, 3, 2 și ultimul va fi 1. Apoi tipăriți ambele liste pentru a verifica ordinea.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Rezultatul funcționării acestui cod este următorul:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Ei bine, ordinea listelor de linkuri este previzibilă și de înțeles. Este comandat conform principiului FIFO. Am început cu 5, deci acest element este primul în linie, apoi merge cu 4 și așa mai departe. Ce putem spune despre ordinea prioritară în coadă? Docs a spus că elementele cozii de prioritate sunt ordonate în funcție de ordinea lor naturală, sau de un Comparator furnizat la momentul construirii cozii. Cu toate acestea, această ordine nu pare a fi „naturală” în sensul sortării liniare. Ne-am aștepta mai degrabă la [1, 2, 3, 4, 5], nu la [1, 2, 4, 5, 3]. Pentru a înțelege de ce ordinea de recuperare este așa cum este, ar trebui să ne amintim acea coadă de prioritate bazată pe un heap. Ce este grămada? Este o structură de date bazată pe arbore binar. Proprietatea principală a mormanului: prioritatea fiecărui părinte este mai mare decât prioritățile copiilor săi. Permiteți-mi să vă reamintesc că un arbore se numește binar complet dacă fiecare părinte are nu mai mult de doi copii, iar umplerea nivelurilor merge de sus în jos (de la același nivel - de la stânga la dreapta). Heap-ul binar se reorganizează de fiecare dată când elemente sunt adăugate sau eliminate din el. În cazul min-heap-ului, cel mai mic element merge la rădăcină indiferent de ordinea inserării acestuia. Coadă de prioritate bazată pe acest min-heap. Aceasta înseamnă că, în cazul elementelor din coadă de numere, primul element al cozii va fi minimul acestor numere. Dacă ștergeți rădăcina, următoarea cea mai mică devine rădăcină.

Să ne întoarcem la exemplul nostru.

Pasul 1. Punem „5” în coada de prioritate. Devine o rădăcină. Pasul 2. Adăugăm „4” în coada de prioritate. 4 <5, deci noul element ar trebui să fie mai mare decât cel mai vechi. 4 devine o rădăcină, 5 este copilul său stâng. Acum structura de date în Java este [4, 5] Pasul 3. Adăugăm „3”. Temporar devine un copil drept al unei rădăcini (4). Cu toate acestea, 3 < 4, așa că ar trebui să-l ridicăm. Schimbă 3 și 4. Acum avem o structură precum [3, 5, 4] Pasul 4. Adăugăm „2”. Devine copil stâng de 5. 2<5, așa că schimbă-le. 2 devine un copil stâng al lui 3, 2 < 3, deci încă un proces de schimb. Acum avem o structură [2,3,4,5] Pasul 5.Adăugăm „1”. Vine de la copilul din dreapta al celor 3 la copilul din stânga al celor 2 și apoi merge la rădăcină. Structura datelor rezultat: [1,2,4,5,3] Procesul de eliminare începe de la o rădăcină și provoacă proceduri inverse. Deci, mai întâi avem 1 ca rădăcină, apoi 2, 3, 4 și în cele din urmă 5. De aceea, folosind removing operation poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

avem „sortat” în ieșirea liniară:

1
2
3
4
5

Deci, coada de prioritate ar putea fi eficientă pentru unele operațiuni. Este nevoie de timp O(log N) pentru a introduce și șterge fiecare element și puteți obține elementul minim în O(1). Iată exemplul complet:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Este important să înțelegeți că cozile prioritare se bazează pe grămezi binare, deci nu păstrează elementele în ordine liniară sortată. Fiecare cale de la rădăcină la frunză este ordonată, dar diferitele moduri de la rădăcină nu sunt. Asta înseamnă că poți obține elementul minim al cozii foarte rapid.

Ce ar trebui să știți despre coada de prioritate. Lista scurtă

• Priority Queue nu permite obiecte NULL.
• Puteți adăuga numai obiecte comparabile în PriorityQueue.
• Coada prioritară este construită ca un min heap, un fel de arbore binar. Elementul minim este o rădăcină. Obiectele cozii de prioritate sunt ordonate implicit în ordine naturală.
• Puteți utiliza Comparator dacă aveți nevoie de comandă personalizată.
• PriorityQueue nu este sigur pentru fire, așa că mai bine folosiți PriorityBlockingQueue pentru a lucra într-un mediu concurent.
• PriorityQueue oferă timp O(log(n)) pentru metodele de adăugare și sondare și O(1) pentru a obține elemente minime.