Мы знаем, что очередь следует за первой моделью, но иногда нам нужно обрабатывать объекты в очереди на основе приоритета. Например, допустим, у нас есть приложение, которое генерирует отчеты о запасах для ежедневной торговой сессии, обрабатывает много данных и требует времени для их обработки. Таким образом, клиенты отправляют запрос в приложение, которое фактически ставится в очередь, но мы хотим обрабатывать премиум-клиентов первыми, а стандартных — после них. Так что в этом случае реализация PriorityQueue в Java может быть действительно полезной.
Класс PriorityQueue был представлен в Java 1.5 и является частью Java Collections Framework . PriorityQueue — это неограниченная очередь, основанная на куче приоритетов, и элементы очереди приоритетов упорядочены по умолчанию в естественном порядке, или мы можем предоставить компаратор для упорядочения во время создания экземпляра очереди.
PriorityQueue не допускает нулевые значения, и мы не можем создавать PriorityQueue объектов, которые не сопоставимы, например, любые пользовательские классы, которые у нас есть. Мы используем java Comparable и Comparator интерфейсы для сортировки объектов, а PriorityQueue использует их для приоритетной обработки его элементов.
Голова приоритетной очереди является наименьшим элементом, основанным на естественном упорядочении или упорядочении на основе компаратора. Если имеется несколько объектов с одинаковым упорядочением, он может произвольно опрашивать любой из них. Когда мы опрашиваем очередь, он возвращает головной объект из очереди.
Размер PriorityQueue не ограничен, но мы можем указать начальную емкость во время его создания. Когда мы добавляем элементы в приоритетную очередь, их емкость автоматически увеличивается.
PriorityQueue не является потокобезопасным , поэтому java предоставляет класс PriorityBlockingQueue который реализует интерфейс BlockingQueue для использования в многопоточной среде java .
Реализация PriorityQueue обеспечивает время O (log (n)) для метода постановки и снятия очереди. Давайте посмотрим пример PriorityQueue для естественного упорядочения, а также с Comparator.
У нас есть наш пользовательский класс Customer , который не предоставляет никаких типов заказов, поэтому, когда мы попытаемся использовать его с PriorityQueue, мы должны предоставить для этого объект сравнения.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
package com.journaldev.collections;public class Customer { private int id; private String name; public Customer(int i, String n){ this.id=i; this.name=n; } public int getId() { return id; } public String getName() { return name; }} |
Мы будем использовать генерацию случайных чисел Java для создания случайных объектов клиентов. Для естественного упорядочения я буду использовать Integer, который также является классом-оболочкой Java .
Вот наш последний тестовый код, который показывает, как использовать PriorityQueue.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
package com.journaldev.collections;import java.util.Comparator;import java.util.PriorityQueue;import java.util.Queue;import java.util.Random;public class PriorityQueueExample { public static void main(String[] args) { //natural ordering example of priority queue Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7); Random rand = new Random(); for(int i=0;i<7;i++){ integerPriorityQueue.add(new Integer(rand.nextInt(100))); } for(int i=0;i<7;i++){ Integer in = integerPriorityQueue.poll(); System.out.println("Processing Integer:"+in); } //PriorityQueue example with Comparator Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator); addDataToQueue(customerPriorityQueue); pollDataFromQueue(customerPriorityQueue); } //Comparator anonymous class implementation public static Comparator<Customer> idComparator = new Comparator<Customer>(){ @Override public int compare(Customer c1, Customer c2) { return (int) (c1.getId() - c2.getId()); } }; //utility method to add random data to Queue private static void addDataToQueue(Queue<Customer> customerPriorityQueue) { Random rand = new Random(); for(int i=0; i<7; i++){ int id = rand.nextInt(100); customerPriorityQueue.add(new Customer(id, "Pankaj "+id)); } } //utility method to poll data from queue private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) { while(true){ Customer cust = customerPriorityQueue.poll(); if(cust == null) break; System.out.println("Processing Customer with ID="+cust.getId()); } }} |
Обратите внимание, что я использую Java-анонимный класс для реализации интерфейса Comparator и создания нашего компаратора на основе идентификатора.
Когда я запускаю над тестовой программой, я получаю следующий вывод:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
|
Processing Integer:9Processing Integer:16Processing Integer:18Processing Integer:25Processing Integer:33Processing Integer:75Processing Integer:77Processing Customer with ID=6Processing Customer with ID=20Processing Customer with ID=24Processing Customer with ID=28Processing Customer with ID=29Processing Customer with ID=82Processing Customer with ID=96 |
Из вывода ясно, что наименьший элемент был во главе и был опрошен первым. Если мы не предоставим компаратор при создании customerPriorityQueue , он выдаст исключение ClassCastException во время выполнения.
|
1
2
3
4
5
6
7
|
Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633) at java.util.PriorityQueue.siftUp(PriorityQueue.java:629) at java.util.PriorityQueue.offer(PriorityQueue.java:329) at java.util.PriorityQueue.add(PriorityQueue.java:306) at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45) at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25) |