Кучи (Binary Heap, PriorityQueue)

Бинарная куча — почти полное двоичное дерево с heap property: в min-heap каждый родитель ≤ детей, в max-heap ≥. Корень всегда содержит минимум (или максимум). Insert и extract-min работают за O(log n), peek — O(1). Это эффективная очередь с приоритетом (priority queue), используемая в Dijkstra, Prim, top-K, schedulers и медиане стрима.

Когда применять / Мотивация

Куча нужна, когда требуется быстро получать «самый приоритетный» элемент при динамических вставках:

Top-K largest/smallest в стриме — min-heap размера K, O(n log K) вместо O(n log n) сортировки.
Dijkstra / Prim — извлекаем вершину с минимальным расстоянием за O(log V).
Median from Data Stream — две кучи (max-heap для нижней половины, min-heap для верхней) дают O(log n) insert и O(1) median.
Task Scheduler — задачи с приоритетами, cooldown, deadlines.
K-way merge — слияние K отсортированных списков/потоков через heap из голов: O(N log K).
Event-driven simulation — приоритет = время события.

Идея / Как работает

Куча хранится в массиве, индексация компактная:

левый ребёнок узла i → 2i + 1
правый ребёнок → 2i + 2
родитель → (i - 1) / 2 (целочисленное)

Это даёт отличную кеш-локальность (всё подряд в памяти) и нулевой overhead на указатели.

Insert (push):

Добавляем элемент в конец массива.
Sift-up: пока новый элемент меньше родителя, меняем местами — идём вверх. Максимум log n шагов.

Extract-min (pop):

Запоминаем heap[0] (минимум).
Перемещаем последний элемент массива на позицию 0.
Sift-down: пока есть ребёнок меньше текущего — меняем с минимальным из детей, идём вниз. Максимум log n шагов.

Build heap из массива размера n — наивно n × O(log n) = O(n log n), но если делать снизу вверх sift-down с предпоследнего уровня — это O(n) (большинство узлов внизу и требуют 1–2 шага, доказательство через геометрический ряд).

Heap visualization (min-heap):
              1                      arr index:  0
             / \
            3   2                                1, 2
           / \ / \
          5  4 6  8                              3, 4, 5, 6
         /
        7                                        7

heap[] = [1, 3, 2, 5, 4, 6, 8, 7]
parent of i=7: (7-1)/2 = 3 → heap[3] = 5 ✓

Реализация

MinHeap class

class MinHeap<T> {
  private heap: T[] = [];
  constructor(private compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any)) {}

  size(): number { return this.heap.length; }
  peek(): T | undefined { return this.heap[0]; }

  push(val: T): void {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }

  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.siftDown(0);
    return min;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1; // битовый сдвиг = деление на 2
      if (this.compare(this.heap[i], this.heap[parent]) >= 0) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }

  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let smallest = i;

      if (left < n && this.compare(this.heap[left], this.heap[smallest]) < 0) {
        smallest = left;
      }
      if (right < n && this.compare(this.heap[right], this.heap[smallest]) < 0) {
        smallest = right;
      }
      if (smallest === i) break;

      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

K-th Largest Element (min-heap размера K)

Идея: хранить K наибольших элементов в min-heap. Корень — k-й наибольший. Если новый элемент больше корня → вытесняем минимум.

function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap<number>();
  for (const num of nums) {
    if (heap.size() < k) {
      heap.push(num);
    } else if (num > heap.peek()!) {
      heap.pop();
      heap.push(num);
    }
  }
  return heap.peek()!;
}

Median from Data Stream (две кучи)

class MedianFinder {
  private lower = new MinHeap<number>((a, b) => b - a); // max-heap (через инвертированный compare)
  private upper = new MinHeap<number>();                 // min-heap

  addNum(num: number): void {
    // Кладём в нижнюю половину, потом балансируем
    if (this.lower.size() === 0 || num <= this.lower.peek()!) this.lower.push(num);
    else this.upper.push(num);

    // Поддерживаем размеры: lower.size ∈ {upper.size, upper.size + 1}
    if (this.lower.size() > this.upper.size() + 1) this.upper.push(this.lower.pop()!);
    else if (this.upper.size() > this.lower.size())  this.lower.push(this.upper.pop()!);
  }

  findMedian(): number {
    if (this.lower.size() > this.upper.size()) return this.lower.peek()!;
    return (this.lower.peek()! + this.upper.peek()!) / 2;
  }
}

Трассировка K-th Largest

nums = [3, 2, 1, 5, 6, 4], k = 2
─────────────────────────────────────
num=3: heap.size=0 < 2 → push(3)         heap=[3]
num=2: heap.size=1 < 2 → push(2)         heap=[2,3]
num=1: peek=2, 1 ≤ 2 → skip               heap=[2,3]
num=5: peek=2, 5 > 2 → pop, push(5)       heap=[3,5]
num=6: peek=3, 6 > 3 → pop, push(6)       heap=[5,6]
num=4: peek=5, 4 ≤ 5 → skip               heap=[5,6]
─────────────────────────────────────
peek() = 5 ✓ (k=2 топовых: {5, 6}, минимум = 5)

Сложность

Операция	Время	Память
push (insert)	O(log n)	—
pop (extract-min)	O(log n)	—
peek (top)	O(1)	—
build_heap (heapify массива)	O(n)	O(1) на месте
decrease-key (если знаем индекс)	O(log n)	—
find arbitrary element	O(n)	—

Top-K через min-heap: O(n log k) времени, O(k) памяти. Гораздо лучше O(n log n) сортировки при k ≪ n.

Heap sort: O(n log n) гарантированно (worst case), O(1) дополнительной памяти (in-place), но не stable и медленнее quicksort на практике из-за плохой кеш-локальности на больших n.

Типичные ошибки и подводные камни

k = 1 — куча избыточна, простой проход за O(n) и Math.max достаточно.
k = n — нужен весь отсортированный массив; куча бессмысленна, полная сортировка проще.
Дубликаты: задача обычно «k-th largest, not distinct» — куча обрабатывает корректно.
Decrease-key не поддерживается стандартной кучей за O(log n) без обратного индекса. В Dijkstra обычно используют lazy deletion: пушим элемент с новым приоритетом, при извлечении проверяем флаг visited и пропускаем устаревшие копии.
Min-heap vs max-heap: для top-K наибольших нужен min-heap размера K (вытесняем минимум кандидатов), не max-heap. Ошибочный выбор инвертирует логику.
Compare function: в JS (a, b) => a - b работает только для чисел. Для строк — a.localeCompare(b). Для объектов — извлекать поле.
Стандартной кучи в JS нет — пишите свою или берите библиотеку. В Python — heapq, в Java — PriorityQueue, в C++ — std::priority_queue.
Изменение элемента после push: куча не отслеживает мутации. Если модифицируете объект, используемый как ключ приоритета, heap property нарушится — нужно явно decrease-key или удалять/вставлять заново.

Follow-up вопросы интервьюера

Top K Frequent Elements. Counter в Map → min-heap размера K на парах (frequency, element). O(n log K).
Merge K Sorted Lists. Min-heap из K голов; извлекаем минимум, добавляем следующий из того же списка. O(N log K).
Find Median from Data Stream. Две кучи (max-heap / min-heap), балансируем размеры. O(log n) insert, O(1) median.
Task Scheduler. Max-heap по частоте + очередь cooldown. Greedy + heap. O(n log 26).
Dijkstra с decrease-key. Indexed Priority Queue (обратный индекс элемент → позиция) или lazy deletion.
Fibonacci Heap vs Binary. Fibonacci даёт O(1) amortized decrease-key и merge — теоретически лучше для Dijkstra. Но огромная константа и сложность реализации делают binary heap практичнее.
QuickSelect vs heap для k-th largest. QuickSelect: average O(n), worst O(n²) без рандомизации. Min-heap: гарантированный O(n log k), O(k) памяти. На стриме (когда n заранее не известно) только heap работает.
Heap vs BST. Heap: O(1) min, O(log n) insert, не отсортирован. BST: O(log n) min/max/successor/predecessor, отсортирован in-order. Heap проще и компактнее для priority queue.
Skyline Problem / Meeting Rooms II. Min-heap по end-time текущих интервалов.

Чеклист на собес

Помню индексацию: parent (i-1)/2, children 2i+1, 2i+2.
Знаю sift-up для insert и sift-down для extract.
Помню build_heap за O(n) (снизу вверх).
Для top-K largest — min-heap размера K (не max-heap).
Помню паттерн «две кучи» для медианы.
Знаю про lazy deletion в Dijkstra.
В JS пишу heap руками (нет встроенного).
Понимаю trade-off heap vs BST vs sorted array.