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

O(log n) per op

Дерево, уложенное в массив, где каждый родитель меньше (или больше) своих детей, поэтому текущий минимум или максимум лежит в корне и всегда доступен за одно чтение, даже когда элементы продолжают прибывать.

Сигналы

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

Шаблон

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

Похоже, но не то

Быстрая сортировка (merge/quick): Куча хранит текущий минимум/максимум, пока данные ещё прибывают (top-k, слияние k списков, текущая медиана); сортировке нужен весь набор целиком заранее, поэтому она заставляет пересортировывать всё при каждом новом элементе.

n до 1e5..1e6 поступлений, нужен текущий минимум/максимум без полной пересортировки -> O(log n) на push/pop, O(n log n) суммарно на n операций.

Изучить этот паттерн