0Pricing
Java Academy · Урок

PriorityQueue для упорядоченной обработки

Используйте PriorityQueue с естественным порядком и пользовательскими компараторами для планирования задач.

«PriorityQueue для упорядоченной обработки» — бесплатный урок Java Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Что такое PriorityQueue?

PriorityQueue по умолчанию является минимальной двоичной кучей: элемент с наименьшим естественным порядком всегда находится в начале. Элементы не сортируются внутри — гарантируется только наличие минимального элемента в начале.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (min)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

Внутренняя структура кучи

PriorityQueue использует минимальную двоичную кучу, хранящуюся в массиве. Родительский элемент с индексом i всегда меньше либо равен своим потомкам с индексами 2i+1 и 2i+2. Это обеспечивает сложность O(log n) для offer/poll и O(1) для peek.

Максимальная куча с обратным компаратором

Чтобы создать максимальную кучу, в которой первым находится наибольший элемент, передайте Comparator.reverseOrder():

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(50);
maxPQ.offer(30);

System.out.println(maxPQ.poll()); // 50 (max)
System.out.println(maxPQ.poll()); // 30

PriorityQueue с пользовательскими объектами

Используйте компаратор для упорядочивания пользовательских записей или классов:

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority) // ascending priority
);
queue.offer(new Job("Backup", 5));
queue.offer(new Job("Alert", 1));
queue.offer(new Job("Report", 3));

System.out.println(queue.poll().name()); // Alert (priority 1)

Операции peek и poll

peek() возвращает первый элемент, не удаляя его. poll() удаляет элемент и возвращает его. Обе операции возвращают null для пустой очереди, в отличие от element()/remove(), которые выбрасывают исключение.

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("banana");
pq.offer("apple");

System.out.println(pq.peek()); // apple (not removed)
System.out.println(pq.peek()); // apple (still there)
System.out.println(pq.poll()); // apple (removed)
System.out.println(pq.peek()); // banana

Пример планирования задач

PriorityQueue идеально подходит для моделирования планирования задач на CPU, когда у задач разные приоритеты:

record Task(String name, int priority) {}

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
scheduler.offer(new Task("Low", 1));
scheduler.offer(new Task("Critical", 10));
scheduler.offer(new Task("Normal", 5));

while (!scheduler.isEmpty()) {
    System.out.println("Processing: " + scheduler.poll().name());
}
// Critical, Normal, Low

K наименьших элементов

PriorityQueue — классический инструмент для поиска K наименьших элементов без полной сортировки массива:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) pq.offer(n);

for (int i = 0; i < k; i++) {
    System.out.print(pq.poll() + " ");
}
// 1 2 3

K наибольших элементов с максимальной кучей

Другой вариант — во время обхода поддерживать минимальную кучу размера K, чтобы найти K наибольших элементов:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
// minHeap now contains the 3 largest: [7, 8, 9]
System.out.println(minHeap); // order may vary

Шаблон алгоритма Дейкстры

Алгоритм поиска кратчайшего пути Дейкстры использует минимальную кучу, чтобы всегда первым обрабатывать непосещённую вершину с наименьшей стоимостью:

record Entry(int node, int cost) {}

PriorityQueue<Entry> pq = new PriorityQueue<>(
    Comparator.comparingInt(Entry::cost)
);
pq.offer(new Entry(0, 0)); // start node, cost 0

while (!pq.isEmpty()) {
    Entry curr = pq.poll();
    System.out.println("Visit node " + curr.node() + " cost=" + curr.cost());
    // expand neighbors...
}

Порядок обхода не определён

Обход PriorityQueue с помощью цикла не возвращает элементы в порядке приоритета — это делает только poll(). Для получения отсортированного результата многократно вызывайте poll вместо использования цикла for-each.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,3,1,4,2));

// WRONG for sorted output:
for (int n : pq) System.out.print(n+" "); // unordered!

// CORRECT:
while (!pq.isEmpty()) System.out.print(pq.poll()+" "); // 1 2 3 4 5

Сводка по производительности

Сложность операций PriorityQueue:

  • offer(e): O(log n)
  • poll(): O(log n)
  • peek(): O(1)
  • contains(e): O(n)
  • remove(e): O(n)

Класс не поддерживает безопасную работу из нескольких потоков — для параллельного доступа используйте PriorityBlockingQueue.

Быстрая проверка

Что гарантируется относительно порядка элементов при обходе PriorityQueue с помощью цикла for-each?

Повторение: PriorityQueue

Основные выводы:

  • PriorityQueue — минимальная куча: первым извлекается наименьший элемент
  • Для максимальной кучи используйте Comparator.reverseOrder()
  • Сложность offer/poll — O(log n), peek — O(1)
  • Классические случаи применения: K-й по величине или наименьший элемент, алгоритм Дейкстры, планирование задач
  • Цикл for-each не возвращает элементы в порядке приоритета — используйте poll()

Часто задаваемые вопросы

Урок «PriorityQueue для упорядоченной обработки» бесплатный?

Да — полный текст урока «PriorityQueue для упорядоченной обработки» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «PriorityQueue для упорядоченной обработки»?

Используйте PriorityQueue с естественным порядком и пользовательскими компараторами для планирования задач. Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «PriorityQueue для упорядоченной обработки»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Внутреннее устройство LinkedList
  2. Операции Deque: стек и очередь
  3. Компромиссы LinkedList и ArrayList
  4. PriorityQueue для упорядоченной обработки
← Назад к Java Academy