Паттерн: Куча и top-K

Признак в условии

• «K самых частых / больших / близких»
• «k-й по величине»
• слияние нескольких отсортированных источников
• нужен минимум из постоянно меняющегося набора

Лестница решений - называть вслух все три

1. Сортировка: O(n log n), пишется за минуту - нормальный первый ответ.
2. Куча размера k: O(n log k) - держим только k лучших.
3. Quickselect или bucket sort по частоте: O(n) в среднем.

Шаблон

В JS кучи нет в стандартной библиотеке, поэтому пишут свою на массиве: дети узла i лежат на 2i+1 и 2i+2, родитель - на (i−1)>>1. push кладёт в конец и всплывает, pop берёт корень, переносит последний элемент в корень и опускает.

Сложность

push и pop - O(log n), peek - O(1), построение из массива - O(n).

Частые ошибки

• при опускании сравнивают только с одним ребёнком
• pop оставляет дыру вместо перемещения последнего элемента
• берут max-кучу там, где для top-K нужна min-куча размера k (и наоборот)

Мнемоника

«Держи k лучших, выкидывай худшего»

Не путать с

• Жадность - куча - инструмент жадности, когда «лучший сейчас» меняется по ходу
• Монотонный стек - если нужен ближайший по позиции, а не k лучших, стек дешевле
• Бинарный поиск - k-й по величине можно искать и поиском по ответу, если элементы в диапазоне

Задачи на этот паттерн

• K самых частых
• k-й по величине
• слияние k отсортированных массивов

Суть

Куча даёт минимум (или максимум) за O(1) и вставку и извлечение за O(log n). Это структура для задач, где нужно постоянно доставать «лучший на сейчас» элемент.

Как распознать по условию

• «k наибольших / наименьших / ближайших / самых частых»;
• «слей k отсортированных списков»;
• «медиана потока»;
• «каждый раз бери самый маленький / ранний / дешёвый» (симуляция, планирование задач);
• Дейкстра.

Куча на массиве

В JS встроенной кучи нет. Шаблон min-кучи:

class MinHeap {
  constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(a[i], a[p]) >= 0) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
        if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

Max-куча: new MinHeap((a, b) => b - a).

Top-K

function kLargest(nums, k) {
  const h = new MinHeap();
  for (const x of nums) {
    h.push(x);
    if (h.size() > k) h.pop();   // выкидываем худшего
  }
  return h.a;
}

Правило: k наибольших → min-куча размера k, k наименьших → max-куча. В вершине худший из лучших, его и вытесняем.

Сложность

Операция	Время
peek	O(1)
push, pop	O(log n)
построить из массива (heapify)	O(n)
top-K	O(n log k)
слияние k списков	O(N log k)

Ловушки

• Взять не ту кучу для top-K.
• Индексы детей 2i, 2i+1 при нумерации с 0.
• Сравнение строк вычитанием даёт NaN: нужен свой компаратор.
• Строить кучу, когда достаточно сортировки: если k близко к n или n маленькое, сортировка проще.

Что спросят на собесе

• Сложность операций кучи и как она устроена в массиве.
• Найди k самых частых элементов.
• Слей k отсортированных списков.
• Как найти медиану потока?