Что такое очередь с приоритетом — и почему её массив выглядит неотсортированным

Ты пишешь планировщик задач для бота. Задачи приходят постоянно, у каждой есть срочность. Нужно всегда брать самую срочную. Первая мысль:

tasks.push(task);
tasks.sort((a, b) => a.priority - b.priority);
const next = tasks.shift();

Работает. Но на каждую новую задачу ты заново сортируешь весь список. Тысяча задач — тысяча сортировок тысячи элементов. Хотя тебе нужен всего один, самый срочный.

Смотри, что неожиданно: чтобы всегда знать самое срочное, список вообще не надо держать отсортированным. Достаточно слабого порядка. Это и есть очередь с приоритетом.

Что такое очередь с приоритетом

Очередь с приоритетом — это очередь, где выходит не тот, кто пришёл первым, а тот, у кого приоритет выше.

Как приёмный покой в больнице. Пришёл с занозой в 9:00 — ждёшь. Привезли с переломом в 9:30 — его берут раньше тебя.

Операций всего три:

• положить элемент;
• посмотреть на самый важный;
• достать самый важный.

Почти всегда внутри лежит куча (heap). Это не «куча хлама», а конкретная структура.

Как работает куча

Куча — это дерево с одним правилом: родитель важнее своих детей. И всё. Между братьями и соседями порядка нет.

Отсюда главное: самый важный элемент всегда на вершине. Посмотреть на него — один шаг.

Хранят кучу в обычном массиве, без всяких узлов. Дети элемента с индексом i лежат на 2i + 1 и 2i + 2, родитель — на (i − 1) / 2 с округлением вниз.

Вот и ответ на вопрос из заголовка. Выведи кучу в консоль, и увидишь что-то вроде [1, 4, 2, 9, 5, 3]. Похоже на ошибку. Но правило соблюдено: 1 меньше 4 и 2, 4 меньше 9 и 5, 2 меньше 3. Куча не отсортирована — и не должна.

Как кладут. Новый элемент ставят в конец массива. Потом он «всплывает»: если он важнее родителя — меняются местами. И так, пока не встанет на место.

Как достают. Забирают вершину. На её место ставят последний элемент. Он «тонет»: меняется с более важным из детей, пока правило не восстановится.

Вот как выглядит «всплытие» в коде — это и есть вся хитрость кучи:

function push(heap, item) {
  heap.push(item);
  let i = heap.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (heap[parent] <= heap[i]) break; // правило соблюдено
    [heap[parent], heap[i]] = [heap[i], heap[parent]];
    i = parent;
  }
}

Цикл идёт только вверх, по одной ветке. Остальное дерево он даже не трогает.

Сколько шагов? Не больше высоты дерева. У кучи на миллион элементов высота около 20. Двадцать перестановок вместо сортировки миллиона.

Где это полезно тебе

Топ-10 из огромного потока. У тебя миллион строк логов, нужны 10 самых медленных запросов. Сортировать всё — держать в памяти миллион. А можно держать кучу ровно из 10 элементов. Новый запрос медленнее самого быстрого в куче? Заменяем. В конце в куче — твой топ-10. Так же считают «хвост» задержек — об этом в статье про перцентиль.

Планировщики и таймеры. Какой таймер сработает следующим? Тот, у кого ближайшее время. Node.js внутри держит свои таймеры именно в очереди с приоритетом. Твои setTimeout — её жители.

Навигаторы. Алгоритм Дейкстры ищет кратчайший путь. На каждом шаге ему нужна ближайшая непосещённая точка. Это ровно операция «достать самое важное».

Очереди задач со срочностью. Платный пользователь, повторная попытка, письмо со сбросом пароля — всё это поводы обработать раньше.

Подвох: одинаковый приоритет

Куча не обещает порядок среди равных. Две задачи с приоритетом 1 могут выйти не в том порядке, в каком пришли.

Если это важно — добавь к приоритету счётчик: [priority, counter++, task]. При равном приоритете победит тот, у кого счётчик меньше, то есть кто пришёл раньше. Так прямо советует документация Python.

Есть ли куча в JavaScript?

Встроенной нет. В Python есть модуль heapq, в Java — класс PriorityQueue. В JS берут пакет вроде @datastructures-js/priority-queue или пишут сами — это около 40 строк. Хороший повод попросить ИИ написать класс и сразу тесты к нему.

Когда хватит обычной сортировки?

Если элементов десятки и ты сортируешь один раз — сортируй, это проще. Куча окупается, когда элементы приходят и уходят постоянно, а нужен всегда один, самый важный.

Куча из этой статьи и «куча» в памяти — одно и то же?

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