Heap (Куча)

Двоичная куча — полное бинарное дерево, где каждый узел не больше (min-heap) или не меньше (max-heap) своих детей. Обычно хранится в массиве: для узла i дети — 2i+1 и 2i+2, родитель — (i-1)/2. Это основа очереди с приоритетом.

Сложности операций

Операция	Сложность
Получить min/max (peek)	O(1)
Вставка (push)	O(log n)
Извлечение min/max (pop)	O(log n)
Построение из массива (heapify)	O(n)

Реализация MinHeap

class MinHeap {
    constructor() { this.h = []; }
 
    push(val) {
        this.h.push(val);
        this._up(this.h.length - 1);
    }
 
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
 
    peek() { return this.h[0]; }
 
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
 
    _down(i) {
        const n = this.h.length;
        while (true) {
            let s = i, l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.h[l] < this.h[s]) s = l;
            if (r < n && this.h[r] < this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

Где применяется

• Top K элементов, k-й наибольший/наименьший
• Слияние K отсортированных списков
• Медиана потока данных (два heap’а)
• Dijkstra, планировщики задач
• Heap Sort

⚠️ В JS нет встроенной PriorityQueue — на собеседовании реализуют MinHeap вручную или обходятся сортировкой для малых K.

См. также

• heap-priority-queue — паттерн и задачи
• heap-sort