Класс PriorityQueue

Что такое PriorityQueue
Конструкторы
Пример класса PriorityQueue

1. Что такое PriorityQueue

PriorityQueue – это класс очереди с приоритетами, реализующий интерфейс Queue. По умолчанию очередь с приоритетами размещает элементы согласно естественному порядку сортировки используя Comparable. Элементу с наименьшим значением присваивается наибольший приоритет. Если несколько элементов имеют одинаковый приоритет, связь определяется произвольно. Обратите внимание, что здесь есть отличие от интерфейса Set. Используя класс Set мы не могли добавлять два одинаковых элемента. В класс PriorityQueue мы можем добавлять одинаковые элементы. Также можно указать специальный порядок размещения, используя Comparator, если естественный порядок сортировки вам не подходит.

2. Конструкторы

Конструкторы класса PriorityQueue:

PriorityQueue() - создает очередь с приоритетами начальной емкостью 11, размещающую элементы согласно естественному порядку сортировки (Comparable).
PriorityQueue(Collection<? extends E> c) - вы можете передать на вход какую-то другую коллекцию.
PriorityQueue(int initialCapacity) - можно указать начальную ёмкость.
PriorityQueue(int initialCapacity, Comparator<? super E> comparator) - можно указать начальную ёмкость и какой-то другой компаратор.
PriorityQueue(PriorityQueue<? extends E> c);
PriorityQueue(SortedSet<? extends E> c).

3. Пример класса PriorityQueue

Давайте рассмотрим пример использования PriorityQueue:

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<String> queue1 = new PriorityQueue<>();
        queue1.offer("Киев");
        queue1.offer("Харьков");
        queue1.offer("Львов");
        queue1.offer("Кременчуг");
        queue1.offer("Кременчуг");
        System.out.print("Priority queue с Comparable: ");
        while (queue1.size() > 0) {
            System.out.print(queue1.remove() + " ");
        }
        System.out.println();

        PriorityQueue<String> queue2
                = new PriorityQueue<>(5, Collections.reverseOrder());
        queue2.offer("Киев");
        queue2.offer("Харьков");
        queue2.offer("Львов");
        queue2.offer("Кременчуг");
        queue2.offer("Кременчуг");
        System.out.print("Priority queue с Comparator: ");
        while (queue2.size() > 0) {
            System.out.print(queue2.remove() + " ");
        }
    }
}

В этом примере мы создаём переменную queue1, объявляя её как Queue. В данной коллекции будут содержаться элементы типа String. С помощью метода offer() мы добавляем пять элементов. В цикле while пока наша коллекция не пуста, мы будем с помощью метода remove() получать элемент из головы очереди одновременно удаляя его.

Далее в этой программе создается ещё одна переменная queue2 с типом PriorityQueue, и в конструктор PriorityQueue передается initialCapacity 5, и другой компаратор. С помощью метода Collections.reverseOrder() задаётся компаратор, который сортирует элементы в порядке обратном от естественного.

Давайте посмотрим на результат этой программы:

Priority queue с Comparable: Киев Кременчуг Кременчуг Львов Харьков 
Priority queue с Comparator: Харьков Львов Кременчуг Кременчуг Киев

Обратите внимание, что элементы мы добавляли в одном порядке, но выводятся на консоль они совсем в другом порядке. Они выводятся на консоль в отсортированном виде. Строку "Кременчуг" я добавила два раза и в выводе мы тоже видим две эти строки.