Руководство Java PriorityQueue
1. PriorityQueue
PriorityQueue - это класс, реализующий interface Queue, поэтому он обладает всеми характеристиками очереди и поддерживает все опциональные операции of Collection. Однако, в отличие от обычной очереди, элементы of PriorityQueue сортируются в порядке возрастания на основе их естественного порядка или в соответствии с предоставленным Comparator (в зависимости от используемого конструктора), поэтому, когда новый элемент вставляется в PriorityQueue, он может находиться не в последней позиции.
![](https://s1.o7planning.com/web-rs/web-image/ru/arf-1193361-vi.webp)
Характеристики, унаследованные от Queue:
- Повторяющиеся элементы разрешены, но элементы null не разрешены.
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable
PriorityQueue - это неограниченная (unbounded) очередь. Элементы сортируются в порядке возрастания, и допускается дублирование элементов.
В основном, PriorityQueue управляет массивом объектов (Object[]) для хранения его элементов. Длина этого массива больше, чем количество элементов очереди. Однако при необходимости этот массив будет заменен другим массивом большей длины.
![](https://s1.o7planning.com/web-rs/web-image/ru/arf-1193386-vi.webp)
PriorityQueue constructors
PriorityQueue()
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
PriorityQueue(Collection<? extends E> c)
PriorityQueue(Comparator<? super E> comparator)
PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)
- Конструктор PriorityQueue(int initialCapacity) создает объект PriorityQueue с внутренним массивом размера initialCapacity. В этом случае все элементы of PriorityQueue должны быть типа Comparable, чтобы иметь возможность сравнивать себя, и элементы null не допускаются.
- Конструктор PriorityQueue(Comparator) создает объект PriorityQueue с размером внутреннего массива по умолчанию 11. В то же время он снабжен Comparator для сравнения элементов друг с другом.
PriorityQueue - это асинхронная очередь, поэтому вы не должны использовать ее в среде multithreading, вместо этого используйте потокобезопасный (thread-safe) класс PriorityBlockingQueue.
// Methods inherited from Collection:
Iterator<E> iterator()
default Spliterator<E> spliterator()
- Iterator, полученный из PriorityQueue, поддерживает все опциональные методы.
- Iterator (или Spliterator), полученный из PriorityQueue, не гарантирует, что он будет проходить (traverse) элементы в порядке приоритета. Если вы хотите перебирать элементы в порядке приоритета, рассмотрите возможность использования Arrays.sort(priorityQueue.toArray()).
![](https://s1.o7planning.com/web-rs/web-image/ru/arf-1193419-vi.webp)
- Queue
- Deque
- ConcurrentLinkedQueue
- BlockingDeque
- BlockingQueue
- TransferQueue
- ArrayDeque
- ConcurrentLinkedDeque
- LinkedList
- ArrayBlockingQueue
- DelayQueue
- LinkedBlockingQueue
- LinkedBlockingDeque
- PriorityBlockingQueue
- SynchronousQueue
- LinkedTransferQueue
2. Examples
String является самосопоставимым типом данных, поскольку он реализует interface Comparable. Таким образом, нет необходимости предоставлять Comparator для PriorityQueue<String>.
PriorityQueueEx1.java
package org.o7planning.priorityqueue.ex;
import java.util.PriorityQueue;
public class PriorityQueueEx1 {
public static void main(String[] args) {
PriorityQueue<String> queue = new PriorityQueue<>();
queue.add("F");
queue.add("D");
queue.add("B");
queue.add("A");
queue.add("C");
String s = null;
// Retrieves and removes the head of this queue
while((s = queue.poll())!= null) {
System.out.println(s);
}
}
}
Output:
A
B
C
D
F
Например: Класс Customer свойствами fullName, loyaltyPoints (Полное имя, накопленные баллы при покупке). Клиентам с более высокими баллами loyaltyPoints будет предоставлен более высокий приоритет.
Customer.java
package org.o7planning.beans;
public class Customer implements Comparable<Customer> {
private String fullName;
private int loyaltyPoints;
public Customer(String fullName, int pointOfPurchase) { //
this.fullName = fullName;
this.loyaltyPoints = pointOfPurchase;
}
public String getFullName() {
return fullName;
}
public int getLoyaltyPoints() {
return loyaltyPoints;
}
@Override
public int compareTo(Customer other) {
if (other == null) {
return -1; // this < other
}
int delta = this.loyaltyPoints - other.loyaltyPoints;
if (delta != 0) {
return - delta;
}
return this.fullName.compareTo(other.fullName);
}
}
PriorityQueueEx2.java
package org.o7planning.priorityqueue.ex;
import java.util.PriorityQueue;
import org.o7planning.beans.Customer;
public class PriorityQueueEx2 {
public static void main(String[] args) {
Customer tom = new Customer("Tom", 200);
Customer jerry = new Customer("Jerry", 50);
Customer donald = new Customer("Donald", 300);
Customer mickey = new Customer("Mickey", 30);
Customer daffy = new Customer("Daffy", 500);
PriorityQueue<Customer> queue = new PriorityQueue<>();
queue.add(tom);
queue.add(jerry);
queue.add(donald);
queue.add(mickey);
queue.add(daffy);
Customer currentCustomer = null;
while((currentCustomer = queue.poll())!= null) { // Retrieves and removes
System.out.println("--- Serving customer: " + currentCustomer.getFullName() + " ---");
System.out.println(" >> Loyalty Points: " + currentCustomer.getLoyaltyPoints());
System.out.println();
}
}
}
Output:
--- Serving customer: Daffy ---
>> Loyalty Points: 500
--- Serving customer: Donald ---
>> Loyalty Points: 300
--- Serving customer: Tom ---
>> Loyalty Points: 200
--- Serving customer: Jerry ---
>> Loyalty Points: 50
--- Serving customer: Mickey ---
>> Loyalty Points: 30
Например: Для элементов, которые не являются самосопоставимыми, необходимо предоставить Comparator для PriorityQueue.
PriorityQueueEx3.java
package org.o7planning.priorityqueue.ex;
import java.util.Comparator;
import java.util.PriorityQueue;
public class PriorityQueueEx3 {
public static void main(String[] args) {
Employee tom = new Employee("Tom", 2000);
Employee jerry = new Employee("Jerry", 500);
Employee donald = new Employee("Donald", 3000);
Employee mickey = new Employee("Mickey", 2000);
Employee daffy = new Employee("Daffy", 5000);
PriorityQueue<Employee> queue = new PriorityQueue<>(new EmployeeComparator());
queue.add(tom);
queue.add(jerry);
queue.add(donald);
queue.add(mickey);
queue.add(daffy);
Employee currentEmployee = null;
while ((currentEmployee = queue.poll()) != null) { // Retrieves and removes
System.out.println("--- Serving employee: " + currentEmployee.getFullName() + " ---");
System.out.println(" >> Salary: " + currentEmployee.getSalary());
System.out.println();
}
}
}
class Employee {
private String fullName;
private int salary;
public Employee(String fullName, int salary) {
this.fullName = fullName;
this.salary = salary;
}
public String getFullName() {
return fullName;
}
public int getSalary() {
return salary;
}
}
class EmployeeComparator implements Comparator<Employee> {
@Override
public int compare(Employee o1, Employee o2) {
if (o1 == o2) {
return 0;
}
if (o1 == null) {
return -1; // o1 < o2
}
if (o2 == null) {
return 1; // o1 > o2
}
int s = o1.getSalary() - o2.getSalary();
if (s != 0) {
return s;
}
return o1.getFullName().compareTo(o2.getFullName());
}
}
Output:
--- Serving employee: Jerry ---
>> Salary: 500
--- Serving employee: Mickey ---
>> Salary: 2000
--- Serving employee: Tom ---
>> Salary: 2000
--- Serving employee: Donald ---
>> Salary: 3000
--- Serving employee: Daffy ---
>> Salary: 5000
Если вы хотите выполнить итерацию по всем элементам of PriorityQueue, не удаляя их, вы можете использовать Iterator или Spliterator, но они не гарантируют порядок приоритета элементов. В этом случае следует использовать Arrays.sort(priorityQueue.toArray()) или Arrays.sort(priorityQueue.toArray(),comparator).
PriorityQueueEx4.java
package org.o7planning.priorityqueue.ex;
import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;
public class PriorityQueueEx4 {
public static void main(String[] args) {
PriorityQueue<String> queue = new PriorityQueue<>();
queue.add("F");
queue.add("D");
queue.add("B");
queue.add("A");
queue.add("C");
System.out.println("--- Using Iterator: ---");
Iterator<String> ite = queue.iterator();
while(ite.hasNext()) {
String e = ite.next();
System.out.println(e);
}
System.out.println("--- Using Arrays.sort(queue.toArray()): ----");
String[] array = new String[queue.size()];
queue.toArray(array);
Arrays.sort(array);
for(String e: array) {
System.out.println(e);
}
}
}
Output:
--- Using Iterator: ---
A
B
D
F
C
--- Using Arrays.sort(queue.toArray()): ----
A
B
C
D
F
В принципе, в дополнение к вышеупомянутым характеристикам PriorityQueue обладает всеми характеристиками of Queue. Методы и связанные с ними примеры о Queue упоминаются в следующей статье:
Руководства Java Collections Framework
- Руководство Java PriorityBlockingQueue
- Руководство Java Collections Framework
- Руководство Java SortedSet
- Руководство Java List
- Руководство Java Iterator
- Руководство Java NavigableSet
- Руководство Java ListIterator
- Руководство Java ArrayList
- Руководство Java CopyOnWriteArrayList
- Руководство Java LinkedList
- Руководство Java Set
- Руководство Java TreeSet
- Руководство Java CopyOnWriteArraySet
- Руководство Java Queue
- Руководство Java Deque
- Руководство Java IdentityHashMap
- Руководство Java WeakHashMap
- Руководство Java Map
- Руководство Java SortedMap
- Руководство Java NavigableMap
- Руководство Java HashMap
- Руководство Java TreeMap
- Руководство Java PriorityQueue
- Руководство Java BlockingQueue
- Руководство Java ArrayBlockingQueue
- Руководство Java TransferQueue
Show More