Какую коллекцию выберешь для частого получения максимума при нечастом добавлении?

Анализ выбора коллекции для получения максимума

Для сценария частого получения максимума при нечастом добавлении следует выбрать PriorityQueue или TreeMap, так как они оптимизированы для именно такого паттерна использования.

PriorityQueue — оптимальный выбор

PriorityQueue — это приоритетная очередь, реализованная на основе binary heap. Это идеальное решение для вашего сценария:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
  (a, b) -> Integer.compare(b, a)  // Max heap (большие элементы в приоритете)
);

// Нечастое добавление
maxHeap.offer(10);  // O(log n)
maxHeap.offer(5);
maxHeap.offer(20);

// Частое получение максимума
int max = maxHeap.peek();  // O(1) — очень быстро!
System.out.println(max);   // 20

// Удаление максимума если нужно
int removed = maxHeap.poll();  // O(log n)

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

• offer() (добавление) — O(log n)
• peek() (получение максимума) — O(1) ✓
• poll() (удаление максимума) — O(log n)

TreeMap — альтернатива с дополнительными возможностями

Если нужен доступ к другим элементам или сортировка, используй TreeMap:

TreeMap<Integer, String> map = new TreeMap<>((a, b) -> Integer.compare(b, a));

map.put(10, "значение");
map.put(5, "значение");
map.put(20, "значение");

// Получить максимум
int max = map.firstKey();  // O(log n)
String value = map.firstEntry().getValue();

// Получить диапазон элементов
NavigableMap<Integer, String> top3 = map.headMap(3);

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

• put() — O(log n)
• firstKey() / firstEntry() — O(log n)
• Навигация и диапазоны — O(log n)

Почему НЕ использовать другие коллекции?

ArrayList: O(n) для поиска максимума — неэффективно при частых обращениях:

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(5);

// Неправильно — O(n)!
int max = list.stream().max(Integer::compare).orElse(0);

HashSet: нет упорядочения, поиск максимума всегда O(n)

TreeSet: логарифмическая сложность для всех операций, но не дает O(1) для peek()

Рекомендация

Выбирай PriorityQueue, если:

• Нужно максимально быстро получать максимум (O(1))
• Добавление элементов редко (O(log n) вполне приемлемо)
• Не нужна сортировка остальных элементов

Выбирай TreeMap, если:

• Нужна гибкость в навигации
• Требуется работать с диапазонами значений
• Нужна возможность обхода в упорядоченном виде

Для вашего сценария PriorityQueue — оптимальный выбор благодаря O(1) для получения максимума при O(log n) для добавления.