PriorityQueue використовується, коли передбачається, що об’єкти будуть оброблені на основі пріоритету. Відомо, що а Черга працює за алгоритмом «перший прийшов – перший вийшов», але іноді елементи черги потрібно обробляти відповідно до пріоритету, тоді в гру вступає PriorityQueue.
PriorityQueue базується на купі пріоритетів. Елементи пріоритетної черги впорядковуються відповідно до природного порядку або за допомогою компаратора, який надається під час побудови черги, залежно від того, який конструктор використовується.
У наведеній нижче черзі пріоритету елемент із максимальним значенням ASCII матиме найвищий пріоритет.
Декларація:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Клас реалізує Серіалізований , Повторювані , Колекція , Черга інтерфейси.
Декілька важливі моменти в черзі пріоритетів такі:
- PriorityQueue не дозволяє значення null.
- Ми не можемо створити PriorityQueue об’єктів, які не можна порівняти
- PriorityQueue — це незв’язані черги.
- Голова цієї черги є найменшим елементом щодо заданого порядку. Якщо кілька елементів мають найменше значення, голова є одним із цих елементів — зв’язки порушуються довільно.
- Оскільки PriorityQueue не є потоково безпечним, Java надає клас PriorityBlockingQueue, який реалізує інтерфейс BlockingQueue для використання в багатопоточному середовищі Java.
- Операції пошуку черги опитують, видаляють, переглядають і елемент отримують доступ до елемента на початку черги.
- Він забезпечує час O(log(n)) для методів додавання та опитування.
- Він успадковує методи від AbstractQueue , AbstractCollection , Колекція, і Об'єкт клас.
Конструктори:
1. PriorityQueue(): Створює PriorityQueue із початковою потужністю за замовчуванням (11), яка впорядковує елементи відповідно до їхнього природного порядку.
PriorityQueue pq = новий PriorityQueue();
2. PriorityQueue (Колекція c): Створює PriorityQueue, що містить елементи у вказаній колекції.
PriorityQueue pq = new PriorityQueue(Collection c);
3. PriorityQueue(int initialCapacity) : Створює PriorityQueue із заданою початковою ємністю, яка впорядковує свої елементи відповідно до їх природного порядку.
PriorityQueue pq = новий PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, Comparator comparator): Створює PriorityQueue із заданою початковою ємністю, яка впорядковує свої елементи відповідно до вказаного компаратора.
PriorityQueue pq = new PriorityQueue(int initialCapacity, Comparator comparator);
5. PriorityQueue(PriorityQueue c) : Створює PriorityQueue, що містить елементи у вказаній черзі пріоритету.
PriorityQueue pq = новий PriorityQueue(PriorityQueue c);
6. PriorityQueue(SortedSet c) : Створює PriorityQueue, що містить елементи в указаному відсортованому наборі.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue (компаратор компаратора): Створює PriorityQueue із початковою потужністю за замовчуванням і елементи якої впорядковуються відповідно до вказаного компаратора.
PriorityQueue pq = new PriorityQueue(Comparator c);
приклад:
Наведений нижче приклад пояснює наступні основні операції пріоритетної черги.
функція стрілки машинопису
- boolean add(E element): цей метод вставляє вказаний елемент у цю пріоритетну чергу.
- public peek(): цей метод отримує, але не видаляє голову цієї черги, або повертає null, якщо ця черга порожня.
- public poll(): цей метод отримує та видаляє голову цієї черги або повертає null, якщо ця черга порожня.
Java
// Java program to demonstrate the> // working of PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue =>new> PriorityQueue();> >// Adding items to the pQueue using add()> >pQueue.add(>10>);> >pQueue.add(>20>);> >pQueue.add(>15>);> >// Printing the top element of PriorityQueue> >System.out.println(pQueue.peek());> >// Printing the top element and removing it> >// from the PriorityQueue container> >System.out.println(pQueue.poll());> >// Printing the top element again> >System.out.println(pQueue.peek());> >}> }> |
>
>Вихід
10 10 15>
Операції над PriorityQueue
Давайте подивимося, як виконати кілька часто використовуваних операцій над класом Priority Queue.
1. Додавання елементів: Щоб додати елемент у пріоритетну чергу, ми можемо використати метод add(). Порядок вставки не зберігається в PriorityQueue. Елементи зберігаються на основі порядку пріоритету, який за замовчуванням є зростаючим.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>Вихід
[0, 1, 1, 1, 2, 1]>
Ми не отримаємо відсортовані елементи, друкуючи PriorityQueue.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>Вихід
[For, Geeks, Geeks]>
2. Видалення елементів: Щоб видалити елемент із пріоритетної черги, ми можемо використати метод remove(). Якщо таких об’єктів декілька, видаляється перший випадок об’єкта. Крім того, метод poll() також використовується для видалення голови та її повернення.
Java
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'Initial PriorityQueue '> + pq);> >// using the method> >pq.remove(>'Geeks'>);> >System.out.println(>'After Remove - '> + pq);> >System.out.println(>'Poll Method - '> + pq.poll());> >System.out.println(>'Final PriorityQueue - '> + pq);> >}> }> |
як перетворити рядок на char
>
>Вихід
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Доступ до елементів: Оскільки Queue дотримується принципу «першим прийшов, першим вийшов», ми можемо отримати доступ лише до голови черги. Щоб отримати доступ до елементів із пріоритетної черги, ми можемо використовувати метод peek().
Java
// Java program to access elements> // from a PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String[] args)> >{> >// Creating a priority queue> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'PriorityQueue: '> + pq);> >// Using the peek() method> >String element = pq.peek();> >System.out.println(>'Accessed Element: '> + element);> >}> }> |
>
>Вихід
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Ітерація PriorityQueue: Існує кілька способів проходження PriorityQueue. Найвідомішим способом є перетворення черги в масив і проходження за допомогою циклу for. Однак черга також має вбудований ітератор, який можна використовувати для проходження черги.
Java
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>' '>);> >}> >}> }> |
>
>Вихід
For Geeks Geeks>
приклад:
Java
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>Вихід
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
Приклади в реальному часі:
Пріоритетна черга — це структура даних, у якій елементи впорядковані за пріоритетом, при цьому елементи з найвищим пріоритетом відображаються на початку черги. Ось кілька реальних прикладів того, де можна використовувати черги пріоритетів:
- Планування завдань: в операційних системах черги пріоритетів використовуються для планування завдань на основі їх рівня пріоритету. Наприклад, завдання з високим пріоритетом, як-от критичне оновлення системи, може бути заплановано перед завданням з нижчим пріоритетом, як-от фоновий процес резервного копіювання. Відділення невідкладної допомоги: у відділенні невідкладної допомоги лікарні пацієнтів сортують залежно від тяжкості їхнього стану, причому в першу чергу надають допомогу тим, хто перебуває в критичному стані. Пріоритетну чергу можна використовувати для керування порядком прийому пацієнтів лікарями та медсестрами. Маршрутизація в мережі: у комп’ютерних мережах пріоритетні черги використовуються для керування потоком пакетів даних. Пакети з високим пріоритетом, такі як голосові та відеодані, можуть мати пріоритет над даними з нижчим пріоритетом, такими як електронна пошта та передача файлів. Транспорт: у системах керування дорожнім рухом пріоритетні черги можна використовувати для керування транспортним потоком. Наприклад, автомобілям екстреної допомоги, таким як машини швидкої допомоги, може бути наданий пріоритет над іншими транспортними засобами, щоб вони могли швидко дістатися до місця призначення. Планування завдань: у системах планування завдань пріоритетні черги можна використовувати для керування порядком виконання завдань. Високопріоритетні завдання, як-от критичні оновлення системи, можуть бути заплановані перед завданнями з нижчим пріоритетом, як-от резервне копіювання даних. Інтернет-ринки: на онлайн-ринках пріоритетні черги можна використовувати для керування доставкою продуктів клієнтам. Замовлення з високим пріоритетом, наприклад експрес-доставка, можуть мати пріоритет над стандартними замовленнями на доставку.
Загалом, черги пріоритетів є корисною структурою даних для керування завданнями та ресурсами на основі їх рівнів пріоритету в різних сценаріях реального світу.
Методи в класі PriorityQueue
| МЕТОД | ОПИС |
|---|---|
| додати (І і) | Вставляє вказаний елемент у цю пріоритетну чергу. |
| очистити() | Видаляє всі елементи з цієї пріоритетної черги. |
| компаратор() | Повертає компаратор, який використовується для впорядкування елементів у цій черзі, або null, якщо цю чергу відсортовано відповідно до природного порядку її елементів. |
| містить? (Об'єкт o) | Повертає true, якщо ця черга містить вказаний елемент. |
| forEach? (Дії споживача) | Виконує задану дію для кожного елемента Iterable, доки всі елементи не будуть оброблені або дія не викличе виняткову ситуацію. |
| ітератор() | Повертає ітератор для елементів у цій черзі. |
| пропозиція? (E e) | Вставляє вказаний елемент у цю пріоритетну чергу. |
| видалити? (Об'єкт o) | Вилучає один екземпляр зазначеного елемента з цієї черги, якщо він присутній. |
| removeAll? (Колекція c) | Видаляє всі елементи цієї колекції, які також містяться у вказаній колекції (необов’язкова операція). |
| removeIf? (фільтр предикатів) | Видаляє всі елементи цієї колекції, які задовольняють заданий предикат. |
| retainAll? (Колекція c) | Зберігає лише елементи цієї колекції, які містяться у вказаній колекції (необов’язкова операція). |
| spliterator() | Створює над елементами в цій черзі сплітатор із пізнім зв’язуванням і швидкий відмову. |
| toArray() | Повертає масив, що містить усі елементи цієї черги. |
| toArray?(T[] a) | Повертає масив, що містить усі елементи цієї черги; тип середовища виконання поверненого масиву – це тип зазначеного масиву. |
Методи, оголошені в класі java.util.AbstractQueue
| МЕТОД | ОПИС |
|---|---|
| addAll(Collection c) | Додає всі елементи вказаної колекції до цієї черги. |
| елемент() | Отримує, але не видаляє голову цієї черги. |
| видалити() | Отримує та видаляє голову цієї черги. |
Методи, оголошені в класі java.util.AbstractCollection
| МЕТОД | ОПИС |
|---|---|
| міститьВсе(Колекція c) | Повертає true, якщо ця колекція містить усі елементи зазначеної колекції. |
| пусто() | Повертає true, якщо ця колекція не містить елементів. |
| toString() | Повертає рядкове представлення цієї колекції. |
Методи, оголошені в інтерфейсі java.util.Collection
| МЕТОД | ОПИС |
|---|---|
| міститьВсе(Колекція c) | Повертає true, якщо ця колекція містить усі елементи зазначеної колекції. |
| дорівнює (об'єкт o) | Порівнює вказаний об’єкт із цією колекцією на рівність. |
| hashCode() | Повертає значення хеш-коду для цієї колекції. |
| пусто() | Повертає true, якщо ця колекція не містить елементів. |
| parallelStream() | Повертає, можливо, паралельний потік із цією колекцією як джерелом. |
| розмір() | Повертає кількість елементів у цій колекції. |
| потік() | Повертає послідовний потік із цією колекцією як джерелом. |
| toArray(генератор IntFunction) | Повертає масив, що містить усі елементи цієї колекції, використовуючи надану функцію генератора для розподілу повернутого масиву. |
Методи, оголошені в інтерфейсі java.util.Queue
| МЕТОД | ОПИС |
|---|---|
| peek() | Отримує, але не видаляє голову цієї черги, або повертає значення null, якщо ця черга порожня. |
| опитування() | Отримує та видаляє голову цієї черги або повертає значення null, якщо ця черга порожня. |
Додатки :
- Реалізація алгоритмів Дейкстри та Прима.
- Збільшити суму масиву після K заперечень
Схожі статті :
- Клас Java.util.PriorityQueue в Java
- Реалізація PriorityQueue через Comparator у Java