Куча (Heap)

Куча (heap) — специализированное полное двоичное дерево, в котором каждый узел удовлетворяет heap property: значение родителя всегда ≤ (min-heap) или ≥ (max-heap) значений его дочерних узлов.

Зачем нужно

Куча — наиболее эффективная структура для задач, требующих многократного нахождения минимума или максимума. Вставка и извлечение элемента — O(log n). Это основа приоритетных очередей, алгоритма Дейкстры и Heap Sort. Без кучи многие алгоритмы работают O(n) вместо O(log n) на каждой операции.

Где используется

  • Приоритетные очереди (priority queue) во всех языках
  • Алгоритм Дейкстры (min-heap для выбора следующей вершины)
  • Алгоритмы Крускала и Прима (MST)
  • Планировщики задач ОС (выбор следующей задачи)
  • Heap Sort — сортировка за O(n log n) с O(1) доп. памятью
  • k-й наибольший/наименьший элемент

Основной контент

Хранение в массиве

Полное двоичное дерево эффективно хранится в массиве:

  • Корень: индекс 0
  • Левый ребёнок узла i: 2*i + 1
  • Правый ребёнок узла i: 2*i + 2
  • Родитель узла i: Math.floor((i - 1) / 2)
Max-heap:
       9
      / \
     6   8
    / \ / \
   5  2 7  4

Массив: [9, 6, 8, 5, 2, 7, 4]

Реализация MinHeap

class MinHeap {
  constructor { this.heap = ; }

  // Вспомогательные
  #parent(i)    { return Math.floor((i - 1) / 2); }
  #leftChild(i) { return 2 * i + 1; }
  #rightChild(i){ return 2 * i + 2; }
  #swap(i, j)   { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }

  // Вставка — O(log n)
  push(val) {
    this.heap.push(val);
    this.#bubbleUp(this.heap.length - 1);
  }

  #bubbleUp(i) {
    while (i > 0 && this.heap[this.#parent(i)] > this.heap[i]) {
      this.#swap(i, this.#parent(i));
      i = this.#parent(i);
    }
  }

  // Просмотр минимума — O(1)
  peek { return this.heap[0]; }

  // Извлечение минимума — O(log n)
  pop {
    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;
  }

  #siftDown(i) {
    const n = this.heap.length;
    let smallest = i;
    const l = this.#leftChild(i), r = this.#rightChild(i);
    if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
    if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
    if (smallest !== i) {
      this.#swap(i, smallest);
      this.#siftDown(smallest);
    }
  }

  get size { return this.heap.length; }
}

const heap = new MinHeap();
[5, 3, 8, 1, 4].forEach(v => heap.push(v));
console.log(heap.pop()); // 1
console.log(heap.pop()); // 3

Heap Sort — O(n log n), O(1) памяти

function heapSort(arr) {
  const n = arr.length;
  // Построение max-heap снизу вверх — O(n)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(arr, n, i);
  // Извлечение элементов
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // макс. в конец
    siftDown(arr, i, 0);
  }
  return arr;
}

Сложность

Операция Время
Вставка O(log n)
Извлечение min/max O(log n)
Просмотр min/max O(1)
Построение из массива (heapify) O(n)
Поиск произвольного элемента O(n)

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

  • Использовать кучу для поиска произвольного элемента — heap не поддерживает O(log n) поиск, только min/max.
  • Путать min-heap и max-heap: по умолчанию в большинстве задач нужна min-heap; в JS нет встроенной.
  • Забывать, что построение кучи из массива — O(n), а не O(n log n) — это важная оптимизация.
  • Не обновлять позицию элемента при decrease-key (нужно для оптимального Дейкстры) — в простой реализации добавляют новую запись и пропускают устаревшие.

Связанные темы

Ресурсы