Реализовать структуру данных, которая принимает поток целых чисел и в любой момент времени позволяет получить топ-5 наибольших значений

10. Поддерживать топ-5 максимальных значений в потоке чисел

Условие задачи:
Необходимо реализовать структуру данных, которая:

принимает поток целых чисел по одному;
в любой момент времени позволяет получить пять наибольших значений среди всех уже добавленных;
не хранит весь входной поток.

Код:

interface I1<T> {
    void putValue(T value);
    List<T> getTopFive();
}

Спойлеры к решению

Подсказки

💡 Хранить все поступившие числа необязательно.
💡 Достаточно постоянно поддерживать только пять максимальных значений.
💡 Для этого удобно использовать PriorityQueue как min-heap.
💡 Минимальный элемент из текущего топ-5 находится в peek().
💡 Если новое число больше минимального элемента топ-5, его нужно заменить.

Решение

class IntegerTopFive implements I1<Integer> {

    private static final int LIMIT = 5;

    private final PriorityQueue<Integer> minHeap =
            new PriorityQueue<>();

    @Override
    public void putValue(Integer value) {
        if (minHeap.size() < LIMIT) {
            minHeap.offer(value);
            return;
        }

        if (value > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(value);
        }
    }

    @Override
    public List<Integer> getTopFive() {
        return minHeap.stream()
                .sorted(Comparator.reverseOrder())
                .toList();
    }
}

Пример использования:

IntegerTopFive topFive = new IntegerTopFive();

topFive.putValue(10);
topFive.putValue(5);
topFive.putValue(20);
topFive.putValue(3);
topFive.putValue(8);
topFive.putValue(25);
topFive.putValue(15);

System.out.println(topFive.getTopFive());

Результат:

[25, 20, 15, 10, 8]

PriorityQueue по умолчанию работает как минимальная куча, поэтому:

minHeap.peek()

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

Пока элементов меньше пяти, новое значение просто добавляется:

if (minHeap.size() < LIMIT) {
    minHeap.offer(value);
}

Когда пять элементов уже есть, новое число интересно только в том случае, если оно больше минимального элемента текущего топ-5:

if (value > minHeap.peek()) {
    minHeap.poll();
    minHeap.offer(value);
}

Таким образом, очередь никогда не содержит больше пяти элементов.

PriorityQueue сама по себе не гарантирует полный порядок элементов при обходе, поэтому для результата создаётся отсортированный список:

minHeap.stream()
        .sorted(Comparator.reverseOrder())
        .toList();

Для каждого нового числа сложность составляет O(log k), где k = 5, то есть фактически константное время. Память — O(k), то есть хранится не более пяти значений.

Если используется Java до версии 16:

return minHeap.stream()
        .sorted(Comparator.reverseOrder())
        .collect(Collectors.toList());