Какова алгоритмическая сложность решения с PriorityQueue для задачи Top K Frequent? Операции offer и poll — какую сложность имеют?

Для задачи Top K Frequent с использованием PriorityQueue алгоритмическая сложность обычно следующая:

• Подсчёт частот элементов — O(N), где N — количество элементов.
• Добавление элементов в PriorityQueue (min-heap) с ограничением размера K — для каждого из M уникальных элементов операция offer занимает O(log K).

Итого, если M — количество уникальных элементов, то общая сложность будет O(N + M log K).

Операции PriorityQueue:

• offer (вставка) — O(log n), где n — текущий размер кучи.
• poll (удаление корня) — O(log n).

В контексте Top K Frequent, размер кучи ограничен K, поэтому операции offer и poll работают за O(log K), что эффективно при K << M.