---
title: "Бинарная куча / очередь с приоритетом"
url: https://algopath.pro/ru/patterns/binary-heap
language: ru
summary: "Куча держит наверху наименьшее значение, а больше ничего не упорядочивает вообще. Вставка и снятие стоят по log n каждая."
updated: 2026-08-24
---

# Бинарная куча / очередь с приоритетом

Куча держит наверху наименьшее значение, а больше ничего не упорядочивает вообще. Вставка и снятие стоят по log n каждая.

## Бинарная куча / очередь с приоритетом: как это работает?

Куча это дерево, лежащее в плоском массиве. Потомки индекса i стоят на 2i плюс один и два.

Единственное правило: родитель сильнее своих потомков. Между собой соседи не упорядочены никак.

Вставка пишет в конец, потом поднимает значение вверх. Оно меняется с родителем, пока сильнее него.

Снятие забирает корень, переносит туда последний элемент и опускает его. Он меняется с лучшим потомком, пока не встанет.

Оба действия идут по одному пути дерева. Высота равна log n, значит и стоимость тоже.

Смысл имеет только корень. Любая другая позиция произвольна.

- `[5]` Кладём 5, 3 и 8. Первое значение становится корнем.
- `[3, 5]` Тройка кладётся и поднимается выше пятёрки.
- `[3, 5, 8]` Восьмёрка остаётся там, куда легла. Родителя она не бьёт.
- `снятие возвращает 3` Корень забирается. Наверх переезжает последний элемент, восьмёрка.
- `[5, 8]` Восьмёрка опускается под пятёрку. Новый корень это минимум остатка.

## Бинарная куча / очередь с приоритетом: когда применять?

- всегда нужен текущий минимум/максимум
- k наименьших/наибольших элементов
- слияние k отсортированных списков
- текущая медиана, пока элементы прибывают
- очередь с приоритетом / самое срочное следующим

## Бинарная куча / очередь с приоритетом: с чем путают?

- **Быстрая сортировка (merge / quick)** - Сортировка один раз даёт полный порядок. Куча отдаёт голову много раз, пока данные ещё идут.
- **Двоичное дерево поиска** - Дерево поиска упорядочивает каждую пару узлов. Куча обещает только корень.
- **Монотонная дек-очередь (максимум/минимум окна)** - Дек умеет выбросить только что устаревший элемент. У кучи дешёвого способа для этого нет.
- **Алгоритм Дейкстры** - Дейкстра это самый известный потребитель кучи. Эта страница про сам контейнер.

## Бинарная куча / очередь с приоритетом: сложность по времени и памяти

n до 1e6 даёт O(log n) на вставку или снятие. Чтение вершины стоит O(1).

## Бинарная куча / очередь с приоритетом: разбор примера

### K ближайших точек к началу координат

Верните k точек, лежащих ближе всего к началу координат.

Список бывает слишком длинным для сортировки, а нужны только k точек.

Держите кучу размера k, на вершине которой худшая из сохранённых точек.

Кладите каждую точку и снимайте вершину, как только куча переросла k. Остаток и есть ответ.

```javascript
function kClosest(points, k) {
    // a max-heap keyed by squared distance: the worst kept point sits on top
    const heap = new MaxHeap((p) => p[0] * p[0] + p[1] * p[1]);

    for (const point of points) {
        heap.push(point);

        if (heap.size() > k) {
            heap.pop(); // drops the farthest, never the closest
        }
    }

    return heap.toArray();
}
```

## Бинарная куча / очередь с приоритетом: частые ошибки

- **Ждут отсортированный массив** Упорядочен только корень. Чтение массива подряд даёт бессмыслицу.
- **Держат все элементы ради вопроса про k** Куча размера k стоит O(n log k). Хранение всех тратит память впустую.
- **Строят кучу не в ту сторону** Для k наибольших нужна min-куча, чтобы худший сохранённый был наверху. Это легко перепутать.
- **Пытаются удалить произвольный элемент** У кучи нет дешёвого способа его найти. Пометьте его мёртвым и пропустите при всплытии.

## Бинарная куча / очередь с приоритетом: задачи с собеседований

- **K-й по величине в потоке** Min-куча размера k, ответ лежит в корне.
- **K ближайших точек к началу** Ограниченная max-куча по квадрату расстояния.
- **Слияние k отсортированных списков** Куча держит головной узел каждого списка.
- **K самых частых элементов** Сначала счётчики, потом куча размера k.
- **Планировщик задач** Самая частая задача идёт первой в каждом раунде.
- **Медиана потока чисел** Две кучи, смотрящие друг на друга через середину.
- **Кратчайший путь Дейкстры** Куча решает, какую вершину закрывать следующей.

## JavaScript

```javascript
function kSmallest(nums, k) {
    const heap = []; // max-heap: keeps the k smallest seen so far
    const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]);
    function push(v) {
        heap.push(v);
        let i = heap.length - 1;
        while (i > 0 && heap[(i - 1) >> 1] < heap[i]) { swap((i - 1) >> 1, i); i = (i - 1) >> 1; }
    }
    function pop() {
        const top = heap[0];
        heap[0] = heap.pop();
        let i = 0;
        while (2 * i + 1 < heap.length) {
            let c = 2 * i + 1;
            if (c + 1 < heap.length && heap[c + 1] > heap[c]) c++;
            if (heap[i] >= heap[c]) break;
            swap(i, c); i = c;
        }
        return top;
    }
    for (const x of nums) {
        push(x);
        if (heap.length > k) pop();
    }
    return heap.slice().sort((a, b) => a - b);
}
```

## Python

```python
import heapq

def k_smallest(nums, k):
    heap = []  # max-heap via negation: keeps the k smallest seen so far
    for x in nums:
        heapq.heappush(heap, -x)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(-x for x in heap)
```

## PHP

```php
function kSmallest(array $nums, int $k): array {
    $heap = new SplMaxHeap(); // keeps the k smallest seen so far
    foreach ($nums as $x) {
        $heap->insert($x);
        if ($heap->count() > $k) {
            $heap->extract();
        }
    }
    $result = [];
    foreach ($heap as $x) {
        $result[] = $x;
    }
    sort($result);
    return $result;
}
```