В чем будет сложность мин кучи? - PullRequest
Новая
       25

В чем будет сложность мин кучи?

0 голосов
/ 15 марта 2019

Какова будет сложность минимальной кучи в моем случае?

Мне нужно выяснить 5 самых маленьких чисел в списке.

Что я делаю, это 

public List<Integer> mins(final List<Integer> list) {
        final PriorityQueue<Integer> mins = new PriorityQueue<>(5, Comparator.reverseOrder());
        for (final int num: list) {
            if (mins.size() > 4) {
                if (mins.peek() > num) {
                    mins.poll();
                    mins.add(num);
                }
            } else {
                mins.add(num);
            }
        }
        final List<Integer> result = new ArrayList<>(mins);
        Collections.sort(result);
        return result;
}

Правильно ли, что сложность фрагмента кода O (nlog5) -> O (n)? Во многих источниках я вижу, что сложность Min Heap равна nlog (n). Верно ли, что сложность Min Heap равна nlog (m), где m - размер кучи?

...