Класс PriorityQueue в Java

Добавьте в PriorityQueue<Integer> числа 5, 1, 4, 2, 3 и выведите очередь через System.out.println(pq) — получится [1, 2, 4, 5, 3], а не [1, 2, 3, 4, 5]. Очередь не сломана: она гарантирует только то, что первым выйдет наименьший элемент, а всё остальное хранит в виде кучи.

PriorityQueue (java.util.PriorityQueue, priority queue — «очередь с приоритетом») — класс из Java 5, реализующий интерфейс Queue на бинарной куче. Элементы извлекаются не в порядке добавления, а по приоритету: по умолчанию первым выходит наименьший элемент в естественном порядке (Comparable), а с Comparator можно задать любой другой. Дубликаты разрешены, null запрещён, класс не потокобезопасен.

Как устроена PriorityQueue: бинарная куча (min-heap)

Внутри PriorityQueue лежит массив Object[], в котором элементы образуют бинарную кучу (binary heap): каждый элемент не больше своих потомков. Для элемента с индексом i потомки находятся в ячейках 2*i + 1 и 2*i + 2, а родитель — в (i - 1) / 2. Поэтому наименьший элемент всегда лежит в ячейке 0 — это голова очереди.

Так выглядит куча после offer(5), offer(1), offer(4), offer(2), offer(3):

массив:  [1, 2, 4, 5, 3]
индекс:   0  1  2  3  4

          1
        /   \
       2     4
      / \
     5   3

Каждый родитель меньше потомков, но между «соседями» порядка нет: 4 стоит раньше 3. Такая куча называется min-heap. Если передать компаратор с обратным порядком, вверху окажется наибольший элемент — это max-heap (пример в разделе PriorityQueue с Comparator).

Новый элемент записывается в конец массива и «всплывает» (sift up), меняясь с родителем, пока тот больше. При poll() голова удаляется, на её место ставится последний элемент и «погружается» (sift down) вниз. Обе операции проходят не больше одного пути от корня до листа, то есть O(log n):

import java.util.PriorityQueue;

public class HeapDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5);
        pq.offer(1);
        pq.offer(4);
        pq.offer(2);
        pq.offer(3);

        System.out.println(pq);        // [1, 2, 4, 5, 3]
        System.out.println(pq.poll()); // 1
        System.out.println(pq);        // [2, 3, 4, 5]
    }
}

Вывод:

[1, 2, 4, 5, 3]
1
[2, 3, 4, 5]

После poll() последний элемент 3 встал в корень, опустился на место двойки, и куча снова корректна. toString() печатает массив кучи как есть, поэтому по выводу очереди нельзя судить о порядке извлечения.

Конструкторы PriorityQueue

У PriorityQueue семь конструкторов: они отличаются начальной ёмкостью, компаратором и источником начальных элементов. Если компаратор не передан, используется естественный порядок Comparable. Начальная ёмкость по умолчанию — 11 элементов, и это не ограничение: массив растёт автоматически.

Когда массив заполняется, он пересоздаётся: пока ёмкость меньше 64, примерно вдвое, дальше — на 50%. Передавать ёмкость в конструктор имеет смысл, когда число элементов известно заранее, — это экономит копирования. Жёстко ограничить размер PriorityQueue конструктором нельзя (способ — в разделе k наибольших элементов).

Пример PriorityQueue: естественный и обратный порядок

В естественном порядке PriorityQueue<String> отдаёт строки по алфавиту (точнее, по кодам символов Unicode), а с компаратором Collections.reverseOrder() — в порядке, обратном естественному. Одинаковые элементы при этом не отбрасываются, в отличие от множеств Set.

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.println("Голова: " + queue1.peek());
        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() + " ");
        }
    }
}

Вывод:

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

Переменная queue1 объявлена типом интерфейса Queue, элементы — строки. Метод offer() добавляет пять элементов, peek() показывает голову без удаления. В цикле while, пока коллекция не пуста, метод remove() извлекает элемент из головы очереди, одновременно удаляя его.

Для queue2 в конструктор передаются начальная ёмкость 5 и компаратор Collections.reverseOrder(), который сортирует элементы в порядке, обратном естественному. Элементы добавлялись в одном порядке, а извлекаются отсортированными, причём «Кременчуг» встречается дважды — как и был добавлен. Ёмкость 5 тоже не мешает: очередь приняла бы и шестой элемент.

Методы PriorityQueue и сложность операций

Добавление и извлечение головы в PriorityQueue выполняются за O(log n), просмотр головы и размер — за O(1), а поиск и удаление произвольного элемента (contains(), remove(Object)) — за O(n), потому что куча не упорядочена для поиска. Так сложность описана и в документации PriorityQueue.

Чем отличаются пары offer/add, poll/remove и peek/element в любых очередях, разобрано в разделе Интерфейс Queue в Java. У PriorityQueue нет методов getFirst() и getLast() из Java 21: класс не реализует Deque и SequencedCollection, и вызов pq.getFirst() не скомпилируется.

PriorityQueue с Comparator: свои объекты и max-heap

Чтобы положить в PriorityQueue собственные объекты, класс должен реализовать Comparable или в конструктор нужно передать Comparator. Компаратор же превращает очередь в max-heap: с Collections.reverseOrder() (или Comparator.reverseOrder()) первым выходит наибольший элемент.

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class TaskQueue {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> tasks =
                new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        tasks.offer(new Task("Отчёт", 3));
        tasks.offer(new Task("Исправить баг в проде", 1));
        tasks.offer(new Task("Код-ревью", 2));

        while (!tasks.isEmpty()) {
            Task t = tasks.poll();
            System.out.println(t.priority() + " " + t.name());
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(List.of(5, 1, 4, 2, 3));
        System.out.println("Максимум: " + maxHeap.peek());
    }
}

Вывод:

1 Исправить баг в проде
2 Код-ревью
3 Отчёт
Максимум: 5

Чтобы задачи с наибольшим числом выходили первыми, достаточно Comparator.comparingInt(Task::priority).reversed(). Как собирать компараторы из comparing(), thenComparing() и reversed(), показано в разделе Comparator.comparing, thenComparing, reversed. Популярную запись max-heap через лямбду (a, b) -> b - a лучше не использовать: на больших по модулю числах вычитание переполняется (почему нельзя писать return a - b), безопасный вариант — (a, b) -> Integer.compare(b, a).

Что будет без Comparable и без компаратора

Компилятор не проверяет, сравнимы ли элементы: new PriorityQueue<Point>() компилируется для любого класса. Ошибка появится только при выполнении:

record Point(int x, int y) {}

PriorityQueue<Point> points = new PriorityQueue<>();
points.offer(new Point(1, 2));
// JDK 11+: java.lang.ClassCastException: class Point cannot be cast to class java.lang.Comparable
// Java 8: первый offer() проходит, исключение бросит второй

В Java 8 первый элемент записывался в массив без сравнения, поэтому ошибка проявлялась на втором offer(), а в современных JDK — сразу. Исправление — реализовать Comparable<Point> или передать компаратор, например Comparator.comparingInt(Point::x).

Порядок обхода: почему итератор не сортирует

Итератор, цикл for-each, toString() и toArray() у PriorityQueue обходят внутренний массив кучи, поэтому порядок элементов в них не совпадает с порядком приоритета. Отсортированно элементы выходят только при последовательных вызовах poll(). Что выведет этот код?

import java.util.List;
import java.util.PriorityQueue;

public class IterationOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : List.of(5, 1, 4, 2, 3)) {
            pq.offer(x);
        }

        for (int x : pq) {
            System.out.print(x + " ");
        }
        System.out.println();

        System.out.println(pq.stream().sorted().toList());

        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
        System.out.println();
        System.out.println("Размер: " + pq.size());
    }
}

Вывод:

1 2 4 5 3
[1, 2, 3, 4, 5]
1 2 3 4 5
Размер: 0

For-each показал массив кучи. stream().sorted() вернул отсортированную копию, не трогая очередь (toList() — с Java 16; на Java 8 используйте collect(Collectors.toList())). Цикл с poll() выдал правильный порядок, но опустошил очередь. Если очередь с компаратором, сортируйте копию тем же компаратором: pq.stream().sorted(pq.comparator()) — при естественном порядке comparator() вернёт null, и sorted(null) бросит NullPointerException, поэтому там нужен просто sorted().

Практический пример: k наибольших элементов

Чтобы найти k наибольших элементов в большом наборе, не сортируя его целиком, используют min-heap размера k: каждый новый элемент добавляют в очередь, а когда размер превысил k, удаляют голову — текущий минимум. В очереди остаются k наибольших, время работы O(n log k), память O(k).

import java.util.List;
import java.util.PriorityQueue;

public class TopK {
    static List<Integer> topK(List<Integer> numbers, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int n : numbers) {
            heap.offer(n);
            if (heap.size() > k) {
                heap.poll();          // выбрасываем наименьший
            }
        }
        return heap.stream().sorted().toList();
    }

    public static void main(String[] args) {
        List<Integer> data = List.of(5, 1, 9, 3, 7, 2, 8);
        System.out.println(topK(data, 3));
        System.out.println(topK(data, 10));
        System.out.println(topK(List.of(), 3));
    }
}

Вывод:

[7, 8, 9]
[1, 2, 3, 5, 7, 8, 9]
[]

Если k больше размера данных, возвращаются все элементы; для пустого списка — пустой результат без исключений. Тот же приём даёт «очередь ограниченного размера» для потока событий: в памяти хранятся только k лучших значений, сколько бы данных ни пришло. Для k наименьших берут max-heap, то есть очередь с Collections.reverseOrder().

Нюансы: null, изменение приоритета, потоки

Три свойства PriorityQueue чаще всего приводят к ошибкам: очередь не принимает null, не замечает изменения полей уже добавленного объекта и не защищена от одновременного доступа из нескольких потоков. Все три не видны компилятору.

null. offer(null) и add(null) бросают NullPointerException: элемент null нельзя сравнить, а poll() и peek() возвращают null как признак пустой очереди. Почему null в очередях опасен, разобрано в разделе Queue и null.

Изменение приоритета. Куча перестраивается только при offer() и poll(). Если изменить поле, по которому сравниваются объекты, уже лежащие в очереди, порядок извлечения станет неверным:

import java.util.Comparator;
import java.util.PriorityQueue;

public class MutablePriority {
    static class Job {
        final String name;
        int priority;
        Job(String name, int priority) { this.name = name; this.priority = priority; }
    }

    public static void main(String[] args) {
        PriorityQueue<Job> jobs = new PriorityQueue<>(Comparator.comparingInt((Job j) -> j.priority));
        Job a = new Job("A", 1);
        jobs.offer(a);
        jobs.offer(new Job("B", 2));
        jobs.offer(new Job("C", 3));

        a.priority = 10;                        // куча об этом не знает
        System.out.println(jobs.peek().name);   // A — хотя у A теперь самый низкий приоритет

        jobs.remove(a);                         // правильно: убрать,
        a.priority = 10;                        // изменить
        jobs.offer(a);                          // и добавить заново
        System.out.println(jobs.peek().name);   // B
    }
}

Вывод:

A
B

Потоки. PriorityQueue не синхронизирована: одновременные offer() и poll() из разных потоков могут повредить кучу. Потокобезопасная очередь с приоритетом — java.util.concurrent.PriorityBlockingQueue: она неограниченна, использует тот же порядок, а её метод take() ждёт, пока в очереди появится элемент. Другие потокобезопасные коллекции перечислены в разделе Потокобезопасные коллекции Java. И ещё одна мелочь: PriorityQueue не переопределяет equals(), поэтому две очереди с одинаковыми элементами не равны (подробнее).

PriorityQueue vs TreeSet

PriorityQueue и TreeSet обе используют Comparable или Comparator, но решают разные задачи. PriorityQueue — куча: быстрый доступ к одному крайнему элементу и дубликаты. TreeSet — красно-чёрное дерево: полностью отсортированный обход, оба конца, поиск за O(log n), но без дубликатов.

Если нужна очередь с приоритетом, которая должна отдавать и минимум, и максимум, PriorityQueue не подходит: берут TreeSet (если дубликатов нет) или TreeMap со счётчиком повторов. Для обычной очереди FIFO без приоритетов используют ArrayDeque.