Skip to main content

Примеры

Куда деваться JavaScript-разработчику, если нужна куча​

В стандарте JavaScript нет встроенного типа «heap/priority queue». Поэтому почти все решают задачи на кучах с помощью пакета @datastructures-js/priority-queue, который предоставляет классы MinPriorityQueue и MaxPriorityQueue — под капотом они реализованы на двоичной куче (GitHub).

Быстрый старт​

npm i @datastructures-js/priority-queue
import { MaxPriorityQueue } from "@datastructures-js/priority-queue";

function lastStoneWeight(stones) {
  const pq = new MaxPriorityQueue({ priority: (v) => v });
  stones.forEach((v) => pq.enqueue(v));

  while (pq.size() > 1) {
    const y = pq.dequeue().element;
    const x = pq.dequeue().element;
    if (y !== x) pq.enqueue(y - x);
  }
  return pq.isEmpty() ? 0 : pq.front().element;
}

Методы, которые пригодятся:

  • enqueue(value) — добавить элемент
  • dequeue().element — снять корень
  • front().element — посмотреть корень
  • size(), isEmpty() — проверить размер/пустоту (npmjs.com)

На LeetCode​

Платформа уже предустанавливает этот пакет, поэтому импорт писать не нужно — классы доступны сразу после запуска кода (Stack Overflow).

Почему это важно​

Без кучи пришлось бы каждый раз искать два максимума линейным поиском (O(n)), что делает задачу «Last Stone Weight» квадратичной. С MaxPriorityQueue мы получаем O(log n) на операцию и общую сложность O(n log n) — то, что нужно для больших входов.

Last Stone Weight​

Условие задачи​

Вам дан массив целых чисел stones, где stones[i] — это вес i-го камня. На каждом ходе берутся два самых тяжёлых камня и сталкиваются:

  • пусть их веса — x и y, причём x ≤ y;
  • если x == y, оба камня разбиваются и исчезают;
  • если x != y, камень x уничтожается, а камень y теряет вес x (становится y − x).

Верните вес последнего оставшегося камня или 0, если камней не осталось.

Ключевая идея​

Нужно многократно находить два максимальных значения. Самый эффективный способ — сохранить все веса в max-куче:

  • pop двух наибольших — O(log n)
  • вычислить новый вес (если камни не оба разбились)
  • снова push остатка — O(log n)

Повторяем, пока в куче не останется ≤ 1 камня.

Почему не подходит простая сортировка​

Отсортировать массив убыванием и идти слева направо не выйдет: после каждого «столкновения» может появиться новый камень, который нужно вставить обратно в общий набор. Куча даёт логарифмическое время на каждую такую вставку и извлечение, что гораздо быстрее линейного поиска максимума в обычном массиве.

Алгоритм​

  1. Поместить все значения из stones в max-кучу.

  2. Пока размер кучи > 1

    1. y = pop(), x = pop() — два самых тяжёлых камня.
    2. Если x != y, добавить y − x обратно в кучу.
    3. Когда цикл закончится, если в куче есть элемент — это ответ, иначе ответ 0.

Анализ сложности​

  • Каждое столкновение уничтожает как минимум один камень ⇒ не более n итераций.
  • В одной итерации выполняются постоянное число операций pop/push, каждая — O(log n).
  • Итоговое время — O(n · log n).
  • Память — O(n) (сама куча). В Python мы, к тому же, пере-используем входной массив stones, поэтому его тоже учитываем в подсчёте памяти.

Не вникайте в детали реализации кучи — главное помнить, какие операции она даёт и как ими пользоваться.

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  const maxHeap = MaxPriorityQueue.fromArray(stones);

  while (maxHeap.size() > 1) {
    const rest = maxHeap.dequeue() - maxHeap.dequeue();

    if (rest > 0) {
      maxHeap.enqueue(rest);
    }
  }

  return maxHeap.isEmpty() ? 0 : maxHeap.dequeue();
};

Minimum Operations to Halve Array Sum​

Условие задачи​

Дан массив положительных целых чисел nums. За одну операцию можно выбрать любой элемент и уменьшить его ровно вдвое. Нужно вернуть минимальное число операций, достаточное для того, чтобы суммарное значение массива стало не менее чем вдвое меньше исходного.

Ключевая идея​

Каждый раз выгоднее всего делить пополам самый большой элемент — так мы снимаем с общей суммы максимальную возможную «долю». То есть задача сводится к многократному извлечению максимума и вставке нового значения, что лучше всего решается при помощи max-кучи:

  • pop максимума — O(log n)
  • уменьшить значение вдвое, скорректировать целевое «остаточное» значение
  • push полученной половины обратно — O(log n)

Такой подход поддерживает упорядоченность после каждой вставки и обеспечивает логарифмическое время на итерацию.

Почему не подходит простая сортировка​

Если сначала отсортировать массив убыванием и идти слева направо, то после каждого деления появляется новое значение, которое нужно вставить обратно в общую последовательность. В обычном массиве это потребовало бы линейного поиска позиции (O(n)), тогда как куча выполняет ту же операцию за O(log n).

Алгоритм​

  1. Вычислить total = sum(nums) и поместить все элементы в max-кучу.

  2. Задать target = total / 2 — именно столько надо «снять» с суммы.

  3. Пока target > 0

    1. x = pop() — текущий максимум;
    2. half = x / 2, target -= half;
    3. push(half) — вернуть половину обратно в кучу;
    4. увеличить счётчик операций.

  4. Когда target ≤ 0, счётчик операций и есть ответ.

Анализ сложности​

  • Каждое извлечение-вставка обходится в O(log n).
  • Количество итераций не превышает n, потому что достаточно поделить каждый элемент хотя бы один раз.
  • Итоговое время — O(n · log n).
  • Память — O(n) (сама куча).
/**
 * @param {number[]} nums
 * @return {number}
 */
var halveArray = function (nums) {
  const startSum = nums.reduce((acc, num) => acc + num);
  const maxHeap = MaxPriorityQueue.fromArray(nums);
  let currentSum = startSum;
  let steps = 0;

  while (currentSum * 2 > startSum) {
    const max = maxHeap.dequeue();
    currentSum -= max / 2;
    maxHeap.enqueue(max / 2);
    steps++;
  }

  return steps;
};