Очередь с приоритетом в Java

Класс PriorityQueue хранит элементы так, что poll всегда забирает «главный» по правилам Comparable или переданного Comparator. Внутри используется куча, поэтому добавление и извлечение стоят порядка O(log n).

Очередь не сортирует весь набор при каждом шаге: минимум лежит в корне, остальной порядок внутри может быть произвольным, пока вы только снимаете голову.

Очередь заявок по срочности, где меньшее число важнее:

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

public class Main {
	public static void main(String[] args) {
		Queue<Integer> urgent = new PriorityQueue<>();
		urgent.offer(30);
		urgent.offer(5);
		urgent.offer(20);
		System.out.println(urgent.poll());
		System.out.println(urgent.poll());
	}
}

Сначала уйдут 5 и 20, хотя вставка шла в другом порядке. Для строк сработает лексикографический порядок String.

Если нужен обратный приоритет, передайте компаратор в конструктор:

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

public class Main {
	public static void main(String[] args) {
		var byDesc = new PriorityQueue<Integer>(
			Comparator.reverseOrder()
		);
		byDesc.offer(10);
		byDesc.offer(40);
		System.out.println(byDesc.poll());
	}
}

Соберите очередь с числами 8, 2, 5 и выведите два первых результата poll.