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

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

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

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

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

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

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

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

Источники: Википедия: Двоичная куча, Документация Python (англ.): heapq

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

function kSmallest(nums: number[], k: number): number[] {
    const heap: number[] = []; // max-heap: keeps the k smallest seen so far
    const swap = (i: number, j: number): void => {
        [heap[i], heap[j]] = [heap[j], heap[i]];
    };
    function push(v: number): void {
        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(): number {
        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);
}

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)

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

    public static List<Integer> kSmallest(int[] nums, int k) {
        // max-heap: keeps the k smallest seen so far
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int x : nums) {
            heap.add(x);
            if (heap.size() > k) heap.poll();
        }
        List<Integer> result = new ArrayList<>(heap);
        Collections.sort(result);
        return result;
    }

    public static List<int> KSmallest(int[] nums, int k) {
        // max-heap via a negated key: keeps the k smallest seen so far
        var heap = new PriorityQueue<int, int>();
        foreach (int x in nums) {
            heap.Enqueue(x, -x);
            if (heap.Count > k) heap.Dequeue();
        }
        var result = new List<int>();
        while (heap.Count > 0) result.Add(heap.Dequeue());
        result.Sort();
        return result;
    }

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

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 отсортированных списков». Решение на нём обычно укладывается в O(log n) per op.

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Бинарная куча / очередь с приоритетом» чаще всего путают с этими паттернами: Быстрая сортировка (merge / quick), Двоичное дерево поиска, Монотонная дек-очередь (максимум/минимум окна) и Алгоритм Дейкстры.

• Быстрая сортировка (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-й по величине в потоке, K ближайших точек к началу, Слияние k отсортированных списков, K самых частых элементов, Планировщик задач, Медиана потока чисел и Кратчайший путь Дейкстры.

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

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

У паттерна «Бинарная куча / очередь с приоритетом» целевая сложность O(log n) per op.

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