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

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

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

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

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

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

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

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

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

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);
}

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

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

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

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

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

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

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 отсортированных списков
• •текущая медиана, пока элементы прибывают
• •очередь с приоритетом / самое срочное следующим

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

• Быстрая сортировка (merge / quick) (Fast sort (merge / quick)): Сортировка один раз даёт полный порядок. Куча отдаёт голову много раз, пока данные ещё идут.
• Двоичное дерево поиска (Binary search tree): Дерево поиска упорядочивает каждую пару узлов. Куча обещает только корень.
• Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min)): Дек умеет выбросить только что устаревший элемент. У кучи дешёвого способа для этого нет.
• Алгоритм Дейкстры (Dijkstra's algorithm): Дейкстра это самый известный потребитель кучи. Эта страница про сам контейнер.

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

• Ждут отсортированный массив

  Упорядочен только корень. Чтение массива подряд даёт бессмыслицу.

• Держат все элементы ради вопроса про k

  Куча размера k стоит O(n log k). Хранение всех тратит память впустую.

• Строят кучу не в ту сторону

  Для k наибольших нужна min-куча, чтобы худший сохранённый был наверху. Это легко перепутать.

• Пытаются удалить произвольный элемент

  У кучи нет дешёвого способа его найти. Пометьте его мёртвым и пропустите при всплытии.

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

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

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

O(log n) per op

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