Суть Чтение реального кода heap и предсказание поведения: баг sift-up, граница цикла build-heap, top-k через heap размера k и аргумент сложности heapify.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небе
◷ 14 min
Баги в heap прячутся в индексной арифметике и границах циклов — перевёрнутый знак, off-by-one в последнем нелистовом узле, путаница min/max. Читайте каждый фрагмент как на ревью: проследите инвариант, затем выберите точный дефект или верное утверждение.
Цель
Потренируйтесь читать код heap на уровне ревью сеньора: заметить sift-up со сравнением не в ту сторону, обосновать границу цикла build-heap, подтвердить, что heap для top-k правильного размера и ориентации, и защитить, почему heapify есть O(n).
Фрагмент 1 — sift-up
// Замысел: min-heap. siftUp восстанавливает свойство после push.function siftUp(heap, i) { while (i > 0) { const parent = Math.floor((i - 1) / 2); if (heap[i] > heap[parent]) { // <-- сравнение [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; } else { break; } }}
Викторина
Completed
Это должно поддерживать MIN-heap, но после push свойство нарушается. В чём дефект?
Heads-up Для массива с индексацией от 0 родитель i — это ровно floor((i-1)/2). floor(i/2) — формула для индексации от 1 и здесь неверна. Арифметика родителя корректна; баг — направление сравнения.
Heads-up При i = 0 вы в корне, у которого нет родителя — остановка на i > 0 верна. Идти до i >= 0 значило бы вычислить родителя корня и выйти за границы. Реальный баг — направление сравнения.
Heads-up Обмен идёт, когда heap[i] > heap[parent], поднимая бо́льшие значения наверх — это поддерживает MAX-heap. Для min-heap условие должно быть heap[i] < heap[parent].
Фрагмент 2 — build-heap
function buildHeap(arr) { // sift-down каждого нелистового узла снизу вверх const start = Math.floor(arr.length / 2) - 1; for (let i = start; i >= 0; i--) { siftDown(arr, i); } return arr;}
Викторина
Completed
Почему цикл стартует с Math.floor(n/2) - 1 и идёт вниз, и что сломается, если стартовать с 0 и идти вверх?
Heads-up Индексы за floor(n/2)-1 — листья без детей, поэтому sift-down на них пустой — включение их лишь тратит константный множитель, но безвредно. Настоящая причина границы в том, что обработка должна идти снизу вверх, чтобы поддеревья уже были корректны; это и гарантирует движение вниз от последнего нелистового.
Heads-up Снизу вверх (от последнего нелистового к корню) — корректный heapify. Сверху вниз с sift-down ломает предусловие, что поддеревья узла уже heap, поэтому массив может остаться не heapify-нутым.
Heads-up Для массивов с индексацией от 0 последний узел — n-1, его родитель — floor((n-1-1)/2) = floor(n/2)-1, это последний узел, имеющий ребёнка. Значит floor(n/2)-1 верно.
Фрагмент 3 — top-k
function topKLargest(nums, k) { const h = new MinHeap(); // min-heap, корень — наименьший for (const x of nums) { h.push(x); if (h.size() > k) h.pop(); // выбрасываем текущий минимум } return h.toArray(); // k наибольших (в порядке heap)}
Викторина
Completed
Для nums = [4, 1, 7, 3, 8, 5] и k = 3 что держит heap в конце и каково время работы?
Heads-up Min-heap используют именно для того, чтобы НАИМЕНЬШИЙ текущий кандидат был в корне и выбрасывался при переполнении сверх k. После всех pop выжившие — k НАИБОЛЬШИХ: {5, 7, 8}.
Heads-up Порядок вставки не решает выживание. Каждое переполнение выбрасывает текущий минимум, поэтому 4 (выброшен, когда доминируют 5,7,8) не выживает. Остаются три наибольших: {5, 7, 8}.
Heads-up Heap никогда не превышает k+1 элементов (при переполнении возвращается к k), поэтому каждый push/pop есть O(log k), что даёт O(n log k) — лучше O(n log n) при k ≪ n.
Фрагмент 4 — сложность heapify
Heap, построенный снизу вверх, вызывает sift-down по разу на нелистовой узел.Число узлов по высоте h (всего n): ~n/2 при h=0, n/4 при h=1, n/8 при h=2, ...стоимость sift-down из узла высоты h есть O(h).Полная работа T(n) = Σ_h (n / 2^(h+1)) · h
Викторина
Completed
Вычисляя сумму T(n) = Σ_h (n / 2^(h+1)) · h, какова сложность build-heap и почему интуиция «n/2 sift-down × O(log n) каждый = O(n log n)» ошибочна?
Heads-up Это считает каждый внутренний узел высоты log n. Но ~n/2 — листья (высота 0), ~n/4 — высота 1 и т.д.; взвешенная сумма Σ h/2^h сходится, давая O(n), а не O(n log n).
Heads-up build-heap затрагивает Θ(n) узлов, поэтому не может быть сублинейным. Итог — O(n) (линейный), а не O(log n).
Heads-up Heap из n узлов имеет высоту ⌈log₂ n⌉, а не n, поэтому ни один узел не опускается более чем на O(log n) уровней. Взвешенная по высотам сумма сходится к O(n).
Итог
Корректность heap живёт в деталях, которые читаешь построчно: сравнение в sift-up должно соответствовать min или max (ребёнок < родитель для min-heap); build-heap должен идти снизу вверх от последнего нелистового на floor(n/2)-1, чтобы поддеревья каждого узла уже были heap; top-k использует MIN-heap размера k и выбрасывает корень при переполнении, оставляя k наибольших за O(n log k); а heapify есть O(n), потому что взвешенная по высотам сумма узлов Σ h/2^h сходится — большинство узлов это дешёвые листья. Проследите инвариант, прежде чем довериться коду.