Ответ
Для сценария частого получения максимума при редких добавлениях оптимальной структурой является PriorityQueue (куча, или приоритетная очередь).
Характеристики PriorityQueue:
- Получение максимума (
peek()): O(1) – быстрая операция. - Вставка (
add()/offer()): O(log n) – логарифмическая сложность приемлема при редких добавлениях. - Удаление максимума (
poll()): O(log n).
Пример реализации max-heap:
import java.util.Collections;
import java.util.PriorityQueue;
// Создание PriorityQueue в порядке убывания (max-heap)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(15);
maxHeap.offer(5);
maxHeap.offer(25);
int currentMax = maxHeap.peek(); // 25 - получение за O(1)
int removedMax = maxHeap.poll(); // 25 - удаление максимума за O(log n)Альтернативы и их ограничения:
TreeSet: Гарантирует O(log n) для вставки и поиска максимума, но не допускает дубликаты.TreeMap<Integer, Integer>с подсчетом элементов: Может использоваться как мультимножество, но сложнее в поддержке.