Научитесь создавать, использовать и понимать, как работает приоритетная очередь в Java. Мы рассмотрим примеры очередей с элементами, хранящимися в естественном порядке, а также в пользовательском порядке с использованием экземпляра Comparator.
// Естественная упорядоченная очередьPriorityQueue<Целое число> числа = new PriorityQueue<>();// Пользовательская упорядоченная очередьComparator<Task> имяComparator = Comparator.comparing(Task::name);PriorityQueue<Целое число> числа = new PriorityQueue<>(nameComparator);
1. Введение
1.1 Что такое PriorityQueue
Класс Java PriorityQueue — это реализация интерфейса неограниченной очереди, которая обрабатывает элементы в очереди на основе их приоритетов. PriorityQueue отличается от других стандартных очередей, которые реализуют алгоритм FIFO(First-In-First-Out).
В PriorityQueue добавленные элементы извлекаются в соответствии с их приоритетами. По умолчанию приоритет определяется естественным порядком элементов. Приоритет по умолчанию может быть переопределен Comparator, предоставленным во время построения очереди.
Важно отметить, что при печати содержимого очереди приоритетов элементы могут не храниться по их приоритетам. Однако элементы всегда извлекаются в отсортированном порядке.
1.2 Пример PriorityQueue
Давайте разберемся, как использовать PriorityQueue в коде приложения для добавления и удаления элементов.
PriorityQueue<Integer> numbers = new PriorityQueue<>();// Add elements with the add() or offer() methodsnumbers.offer(1);numbers.add(3);numbers.add(2);System.out.println("PriorityQueue: " + numbers);// Examine the items without fremoving from queueSystem.out.println("Item: " + numbers.peek());// Retrieve the items and remobve from queueSystem.out.println("Item: " + numbers.poll());System.out.println("Item: " + numbers.poll());System.out.println("Item: " + numbers.poll());Вывод программы:
PriorityQueue: [1, 3, 2]Item: 1Item: 1Item: 2Item: 3
2. Особенности PriorityQueue
Давайте отметим несколько важных особенностей PriorityQueue.
- PriorityQueue — это неограниченная очередь, которая динамически растет.
- Начальная емкость по умолчанию — «11», ее можно переопределить с помощью параметра initialCapacity в соответствующем конструкторе.
- Значение null не допускается.
- По умолчанию элементы в приоритетной очереди упорядочены в естественном порядке.
- Элементы очереди должны быть Comparable, чтобы определить их приоритеты, когда Comparator не используется для пользовательского упорядочивания. Это может привести к ClassCastException
- Операции извлечения из очереди опрашивают, удаляют, считывают и получают доступ к элементу, находящемуся в начале очереди.
- Головой PriorityQueue является наименьший элемент на основе естественного порядка или порядка на основе компаратора.
- Если имеется несколько объектов с одинаковым приоритетом, то очередь может опросить любой из них случайным образом.
- PriorityQueue не является потокобезопасным. Используйте PriorityBlockingQueue в параллельной среде.
- Он обеспечивает производительность O(log(n)) для методов сложения и опроса.
- Итератор, предоставленный в методе iterator(), не гарантирует обход элементов приоритетной очереди в каком-либо определенном порядке. Если вам нужен упорядоченный обход, рассмотрите возможность использования Arrays.sort(pq.toArray()).
3. Различные способы создания PriorityQueue
Обычно мы рассматриваем порядок элементов в очереди как решающий фактор для создания приоритетной очереди. Основанная на естественном или пользовательском порядке, приоритетная очередь может быть создана двумя способами:
3.1. PriorityQueue с Comparable для естественного упорядочивания
Для создания приоритетной очереди используйте один из следующих конструкторов:
- PriorityQueue(): создает экземпляр с начальной емкостью по умолчанию(11) с элементами, отсортированными в естественном порядке.
- PriorityQueue(емкость): создает экземпляр с указанной начальной емкостью, элементы которого отсортированы в естественном порядке.
PriorityQueue<Integer> numbers = new PriorityQueue<>();
Например, у нас есть запись Task, которая реализует интерфейс Comparable и реализует логику сравнения, используя свое поле приоритета.
record Task(long id, String name, int priority) implements Comparable<Task> {@Overridepublic int compareTo(Task other) {return Integer.compare(other.priority, this.priority);}}Когда мы добавляем несколько задач в очередь приоритетов и извлекаем их, мы получаем задачи, основанные на приоритете.
PriorityQueue<Task> priorityQueue = new PriorityQueue<>();priorityQueue.add(new Task(10001, "Task 1", 5));priorityQueue.add(new Task(10002, "Task 2", 1));priorityQueue.add(new Task(10003, "Task 3", 10));while(!priorityQueue.isEmpty()) {System.out.println(priorityQueue.poll());}Вывод программы:
Task[id=10003, name=Task 3, priority=10]Task[id=10001, name=Task 1, priority=5]Task[id=10002, name=Task 2, priority=1]
3.2. PriorityQueue с компаратором для индивидуального заказа
Если мы хотим определить индивидуальный порядок приоритетов, отличный от естественного порядка объектов, мы можем использовать Comparator.
Например, мы можем определить порядок сортировки задач по полю идентификатора задачи следующим образом:
Comparator<Task> idComparator = Comparator.comparing(Task::id);
Мы передаем экземпляр компаратора конструктору PriorityQueue для обеспечения нового порядка сортировки.
PriorityQueue<Task> priorityQueue = new PriorityQueue<>(idComparator);priorityQueue.add(new Task(10001, "Task 1", 5));priorityQueue.add(new Task(10003, "Task 3", 10));priorityQueue.add(new Task(10002, "Task 2", 1));while(!priorityQueue.isEmpty()) {System.out.println(priorityQueue.poll());}Вывод программы подтверждает, что, хотя задачи были добавлены со случайными идентификаторами, они извлекаются в правильном порядке.
Task[id=10001, name=Task 1, priority=5]Task[id=10002, name=Task 2, priority=1]Task[id=10003, name=Task 3, priority=10]
4. Когда использовать PriorityQueue
Вот несколько сценариев, в которых использование PriorityQueue может быть полезным:
- Планирование задач: при планировании задач на основе их приоритета PriorityQueue может быть полезен для эффективного определения следующей задачи с наивысшим приоритетом.
- Алгоритм поиска A*: это популярный алгоритм поиска пути, используемый в различных приложениях, таких как планирование маршрутов и разработка игр. PriorityQueue может расставлять приоритеты узлов на основе их общей оценочной стоимости от начала до цели.
- Алгоритм Дейкстры: находит кратчайший путь в графе от одного источника ко всем остальным узлам. PriorityQueue эффективно выбирает следующий узел с кратчайшим расстоянием во время выполнения алгоритма.
5. Заключение
В этом руководстве по очередям Java мы научились использовать класс PriorityQueue, который может хранить элементы либо в естественном порядке по умолчанию, либо в пользовательском порядке, указанном компаратором.
Пишите мне свои вопросы в комментариях.