Черги пріоритетів у Java, пояснені на прикладах

Черги пріоритетів дуже часто використовуються в реальних програмах. У цій статті ми дізнаємося, що таке пріоритетні черги та як ми можемо використовувати їх у Java.

Перш ніж ми обговоримо, що таке пріоритетна черга, давайте подивимося, що таке звичайна черга.

Звичайна черга слідує за структурою перший вихід (FIFO). Це означає, що якщо 3 повідомлення - m1, m2 та m3 - потрапляють у чергу в такому порядку, то вони виходять із черги в точно такому ж порядку.

Навіщо нам черги?

Скажімо, у нас є виробники даних (наприклад, коли користувач натискає веб-сторінку), які надзвичайно швидко. Але тоді ми хочемо згодом споживати ці дані повільнішими темпами.

У цьому випадку виробник виштовхує всі повідомлення в чергу, а споживач споживає ці повідомлення пізніше з черги повільнішими темпами.

Що таке пріоритетна черга?

Як уже згадувалося раніше, звичайна черга має структуру first in first out. Але в деяких сценаріях ми хочемо обробляти повідомлення в черзі на основі їх пріоритету, а не на основі того, коли повідомлення потрапило в чергу.

Черги пріоритетів допомагають споживачам спочатку споживати повідомлення з вищим пріоритетом, а потім повідомлення з нижчим пріоритетом.

Черги пріоритетів у Java

Тепер давайте подивимось фактичний код Java, який покаже нам, як використовувати черги пріоритетів.

Черги в пріоритеті із природним впорядкуванням

Ось код, що показує, як створити просту чергу пріоритетів для рядків

private static void testStringsNaturalOrdering() { Queue testStringsPQ = new PriorityQueue(); testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy"); System.out.println("Strings Stored in Natural Ordering in a Priority Queue\n"); while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); } }

Перший рядок повідомляє нам, що ми створюємо пріоритетну чергу:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue доступний у пакеті java.util.

Далі ми додаємо 5 рядків у довільному порядку до черги пріоритетів. Для цього ми використовуємо функцію add (), як показано нижче:

testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy");

Для того, щоб отримати останній пункт із черги, ми використовуємо функцію poll (), як показано нижче:

testStringsPQ.poll()

poll () надасть нам останній елемент, а також видалить його з черги. Якщо ми хочемо отримати останній елемент у черзі, не видаляючи його, ми можемо скористатися функцією peek () :

testStringsPQ.peek()

Нарешті, ми роздруковуємо всі елементи з черги за допомогою функції poll (), як показано нижче:

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

Ось результат вищезазначеної програми:

1234 23bc abcd abxy zzxx

Оскільки ми не сказали черзі пріоритетів, як визначити пріоритет її вмісту, вона використовувала природне впорядкування за замовчуванням. У цьому випадку це повернуло нам дані у порядку зростання рядків. Це не той самий порядок, коли елементи були додані до черги.

А як щодо замовлення на замовлення?

Це також можливо, і ми можемо зробити це за допомогою компаратора.

Давайте створимо цілу чергу пріоритетів зараз. Але цього разу давайте отримаємо результат у порядку зменшення значення.

Для цього спочатку нам потрібно створити цілочисельний порівняльник:

 static class CustomIntegerComparator implements Comparator { @Override public int compare(Integer o1, Integer o2) { return o1 < o2 ? 1 : -1; } }

Для того, щоб створити компаратор, ми реалізуємо інтерфейс компаратора і замінюємо метод порівняння .

Використовуючи o1 <o2? 1: -1 отримаємо результат у порядку спадання. Якби ми використовували o1> o2? 1: -1, тоді ми отримали б результат у порядку зростання

Тепер, коли у нас є компаратор, нам потрібно додати цей компаратор до черги пріоритетів. Ми можемо зробити це так:

Queue testIntegersPQ = new PriorityQueue(new CustomIntegerComparator());

Ось решта коду, який додає елементи до черги пріоритетів і друкує їх:

 testIntegersPQ.add(11); testIntegersPQ.add(5); testIntegersPQ.add(-1); testIntegersPQ.add(12); testIntegersPQ.add(6); System.out.println("Integers stored in reverse order of priority in a Priority Queue\n"); while (!testIntegersPQ.isEmpty()) { System.out.println(testIntegersPQ.poll()); }

Результати роботи вищезазначеної програми наведені нижче:

12 11 6 5 -1

Ми бачимо, що компаратор добре виконав свою роботу. Тепер черга пріоритетів дає нам цілі числа у порядку зменшення.

Черга пріоритетів з об'єктами Java

До цього моменту ми бачили, як ми можемо використовувати рядки та цілі числа з пріоритетними чергами.

У реальних програмах ми, як правило, використовуємо пріоритетні черги зі спеціальними об'єктами Java.

Спершу створимо клас CustomerOrder, який використовується для зберігання деталей замовлення клієнта:

public class CustomerOrder implements Comparable { private int orderId; private double orderAmount; private String customerName; public CustomerOrder(int orderId, double orderAmount, String customerName) { this.orderId = orderId; this.orderAmount = orderAmount; this.customerName = customerName; } @Override public int compareTo(CustomerOrder o) { return o.orderId > this.orderId ? 1 : -1; } @Override public String toString() { return "orderId:" + this.orderId + ", orderAmount:" + this.orderAmount + ", customerName:" + customerName; } public double getOrderAmount() { return orderAmount; } }

Це простий клас Java для зберігання замовлень клієнтів. Цей клас реалізує порівнянний інтерфейс, так що ми можемо вирішити, на основі чого цей об'єкт потрібно впорядковувати в черзі пріоритетів.

Впорядкування визначається функцією compareTo у наведеному вище коді. Рядок o.orderId> this.orderId? 1: -1 вказує, що замовлення слід сортувати на основі порядку зменшення поля orderId

Нижче наведено код, який створює пріоритетну чергу для об'єкта CustomerOrder:

CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

У наведеному вище коді створено три замовлення клієнтів, які додані до черги пріоритетів.

Коли ми запускаємо цей код, ми отримуємо такий результат:

orderId:3, orderAmount:50.0, customerName:customer3 orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1

Як і слід було очікувати, результат надходить у порядку зменшення orderId .

Що робити, якщо ми хочемо визначити пріоритети на основі orderAmount?

Це знову сценарій реального життя. Скажімо, що за замовчуванням об’єкт CustomerOrder має пріоритет за допомогою orderId. Але тоді нам потрібен спосіб, за допомогою якого ми можемо визначити пріоритети на основі orderAmount.

Ви можете відразу подумати, що ми можемо змінити функцію compareTo у класі CustomerOrder c для замовлення на основі orderAmount.

Але класу CustomerOrder c можна використовувати в декількох місцях програми, і це заважатиме роботі іншої програми, якщо ми безпосередньо модифікуємо функцію compareTo .

Рішення цього досить просте: ми можемо створити новий спеціальний порівняльник для класу CustomerOrder і використовувати його разом із чергою пріоритетів

Нижче наведено код спеціального компаратора:

 static class CustomerOrderComparator implements Comparator { @Override public int compare(CustomerOrder o1, CustomerOrder o2) { return o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; } }

Це дуже схоже на користувальницький порівняльник цілих чисел, який ми бачили раніше.

Рядок o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1;вказує на те, що нам потрібно розставити пріоритети на основі порядку зменшення orderAmount .

Нижче наведено код, який створює пріоритетну чергу:

 CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(new CustomerOrderComparator()); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code we are passing the comparator to the priority queue in the following line of code:

Queue customerOrders = new PriorityQueue(new CustomerOrderComparator());

Below is the result when we run this code:

orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1 orderId:3, orderAmount:50.0, customerName:customer3

We can see that the data comes in descending order of the orderAmount.

Code

All the code discussed in this article can be found in this GitHub repo.

Congrats ?

You now know how to use priority queues in Java.

About the author

I love technology and follow the advancements in the field. I also like helping others with my technology knowledge.

Feel free to connect with me on my LinkedIn account //www.linkedin.com/in/aditya1811/

You can also follow me on twitter //twitter.com/adityasridhar18

Feel free to read more of my articles on my blog at adityasridhar.com.