Построение кучи (Heapify)

Преобразование массива в max-heap за O(n) — быстрее чем n insertов O(n log n). Алгоритм: идём с конца от последнего не-листа (n/2-1 до 0), применяем sift-down к каждому узлу. Sift-down (или percolate-down): сравниваем узел с детьми, меняем с большим ребёнком, рекурсивно до листа или heap property. Доказательство O(n): половина узлов на последнем уровне (0 операций), четверть на предпоследнем (1 операция), итого Σ(n/2^(h+1))·h = O(n). Используется в HeapSort phase 1