Куча
Полное двоичное дерево, где каждый родитель ≤ (или ≥) своих детей — даёт O(1) доступ к корню. Хранится в плоском массиве без указателей: для узла с индексом i родитель находится в ⌊(i−1)∕2⌋, левый ребёнок в 2i+1, правый в 2i+2. Структура, не операции.
Вы знаете, что деревья имеют форму. Теперь представьте дерево, сформированное так компактно, что вы можете сохранить его в массиве вообще без указателей. И представьте дерево, сделанное так, что корень всегда является наименьшим (или наибольшим) элементом. Никакого поиска, никаких сравнений — он прямо там на индексе 0. Это куча. Она объединяет две идеи: определённую форму (полное двоичное дерево) и определённое правило упорядочения (свойство кучи). Вместе они дают O(1) доступ к минимуму или максимуму, и хитрое кодирование массива означает отсутствие потраченного впустую пространства.
После этого урока вы сможете объяснить, что такое полное двоичное дерево, сформулировать свойство кучи для мин-куч и макс-куч, использовать арифметику индексов для поиска индексов родителя и детей в куче на основе массива, построить небольшую кучу вручную и проверить, что свойство кучи выполняется, визуализировать связь между структурой дерева и плоским массивом, предсказать, где в массиве кучи находятся корень, минимум и максимум, и узнать кучу, когда вы её видите.
Что такое куча?
Куча — это двоичное дерево, которое удовлетворяет двум свойствам:
- Свойство формы (полное двоичное дерево): Каждый уровень полностью заполнен, кроме, возможно, последнего уровня, который заполняется слева направо.
- Свойство кучи: Каждый родитель меньше или равен своим детям (в мин-куче) или больше или равен своим детям (в макс-куче).
Вместе эти два правила дают главную гарантию: корень всегда является экстремальным элементом. Без свойства формы трюк с массивом ломается; без свойства порядка теряется O(1)-доступ к минимуму или максимуму.
Что такое полное двоичное дерево?
Полное двоичное дерево — это двоичное дерево, где:
- Каждый уровень, кроме возможно последнего, полностью заполнен.
- Если последний уровень не полный, его узлы заполняются слева направо (без пропусков).
Пример: полное дерево с 7 узлами:
1
/ \
2 3
/ \ / \
4 5 6 7Все уровни 0–2 полны. Это полное. Если бы у нас было дерево типа:
1
/ \
2 3
/ \
4 5Это НЕ полное, потому что узел 3 имеет правого ребёнка (5), но узел 2 не имеет правого ребёнка.
Свойство кучи
В мин-куче каждый родитель меньше или равен своим детям. Это означает, что наименьший элемент всегда находится в корне.
В макс-куче каждый родитель больше или равен своим детям. Это означает, что наибольший элемент всегда находится в корне.
Пример мин-кучи:
1 (наименьший)
/ \
3 2
/ \
5 4Каждый родитель ≤ своих детей: 1 ≤ (3, 2), 3 ≤ (5, 4), 2 ≤ (ничего). Минимум всегда в корне.
Представление массива
Потому что куча — это полное двоичное дерево, она может быть сохранена в плоском массиве без указателей. Мы просто раскладываем узлы в порядке поуровневого обхода (уровень за уровнем, слева направо). Корень находится в индексе 0.
Для узла с индексом i:
- Индекс родителя =
Math.floor((i - 1) / 2) - Индекс левого ребёнка =
2 * i + 1 - Индекс правого ребёнка =
2 * i + 2
Пример: мин-куча выше в виде массива:
Индекс: 0 1 2 3 4
Значение: [1, 3, 2, 5, 4]Проверьте связи:
- Индекс 0 (значение 1) имеет детей в индексах 1 (значение 3) и 2 (значение 2). Родитель = floor((1-1)/2) = 0. Родитель = floor((2-1)/2) = 0. ✓
- Индекс 1 (значение 3) имеет детей в индексах 3 (значение 5) и 4 (значение 4). Родитель = floor((3-1)/2) = 1. Родитель = floor((4-1)/2) = 1. ✓
- Индекс 2 (значение 2) не имеет детей (индексы 5 и 6 не существуют). Родитель = floor((2-1)/2) = 0. ✓
Почему формулы работают
В порядке поуровневого обхода, если вы пронумеруете узлы 0, 1, 2, …, структура полного двоичного дерева означает:
- Узел 0 — корень.
- Узлы 1 и 2 — дети узла 0.
- Узлы 3 и 4 — дети узла 1.
- Узлы 5 и 6 — дети узла 2.
- И так далее.
Паттерн состоит в том, что дети узла i находятся в индексах 2*i + 1 и 2*i + 2. Работая в обратном направлении, родитель узла j находится в индексе floor((j - 1) / 2). Когда встретишь эти формулы в коде, не принимай их как магию — это просто нумерация обходом в ширину плюс одна строка алгебры.
Построение кучи с нуля
Построим мин-кучу вручную и сохраним её в массиве:
// Мин-куча сохранена как массив const minHeap = [1, 3, 2, 5, 4]; // Вспомогательные функции для арифметики индексов function parentIndex(i) { return Math.floor((i - 1) / 2); } function leftChildIndex(i) { return 2 * i + 1; } function rightChildIndex(i) { return 2 * i + 2; } // Доступ к корню (минимум в мин-куче) console.log("Корень (минимум):", minHeap[0]); // 1 // Доступ к детям индекса 1 (значение 3) console.log("Значение в индексе 1:", minHeap[1]); // 3 console.log("Левый ребёнок индекса 1:", minHeap[leftChildIndex(1)]); // 5 console.log("Правый ребёнок индекса 1:", minHeap[rightChildIndex(1)]); // 4 // Доступ к родителю индекса 3 (значение 5) console.log("Значение в индексе 3:", minHeap[3]); // 5 console.log("Родитель индекса 3:", minHeap[parentIndex(3)]); // 3 - L2 Куча — это просто массив. Индекс 0 — корень.
- L5 Формула индекса родителя: floor((i - 1) / 2).
- L8 Формула индекса левого ребёнка: 2*i + 1.
- L11 Формула индекса правого ребёнка: 2*i + 2.
- L15 Корень всегда в индексе 0.
- L18 Доступ к детям любого узла с помощью формул индексов.
- L23 Навигация от ребёнка к его родителю.
Большая куча
Построим макс-кучу с 10 узлами. Максимум всегда в корне.
// Макс-куча сохранена как массив const maxHeap = [50, 30, 20, 10, 15, 8, 5, 2, 3, 7]; function parentIndex(i) { return Math.floor((i - 1) / 2); } function leftChildIndex(i) { return 2 * i + 1; } function rightChildIndex(i) { return 2 * i + 2; } // Проверьте свойство кучи: родитель >= дети for (let i = 0; i < maxHeap.length; i++) { const left = leftChildIndex(i); const right = rightChildIndex(i); if (left < maxHeap.length) { console.log(`Родитель ${maxHeap[i]} >= левый ребёнок ${maxHeap[left]}: ${maxHeap[i] >= maxHeap[left]}`); } if (right < maxHeap.length) { console.log(`Родитель ${maxHeap[i]} >= правый ребёнок ${maxHeap[right]}: ${maxHeap[i] >= maxHeap[right]}`); } } - L2 Макс-куча: каждый родитель >= его дети.
- L16 Цикл через каждый узел.
- L17 Вычислите индексы левого и правого детей.
- L20 Если левый ребёнок существует, проверьте свойство кучи.
- L23 Если правый ребёнок существует, проверьте, что родитель >= ребёнок.
const minHeap = [1, 3, 2, 5, 4]; // Навигация от корня к узлу в индексе 3 let current = 0; // Начните с корня let target = 3; // Индекс 3 имеет значение 5 // Найдите родителя: floor((3-1)/2) = 1 Временная сложность
В массиве кучи:
- Доступ к корню (минимум/максимум): O(1). Он всегда в индексе 0.
- Арифметика индексов (поиск родителя/ребёнка): O(1). Одно деление или умножение.
- Доступ к любому узлу по индексу: O(1). Прямой доступ к массиву.
Пространственная сложность
- Сохранение кучи: O(n), где n — количество узлов. Массив использует O(n) пространства, и указатели не нужны.
Примечание: Операции добавления или удаления элементов в куче (push, pop, sift) НЕ охвачены в этом уроке; они в центре внимания следующего урока (08/02). Здесь мы охватываем только структуру и O(1) арифметику индексов.
В полном двоичном дереве с 7 узлами, сколько узлов должно быть на уровне 0 и уровне 1 (корень и его дети)?
В куче на основе массива с массивом [10, 20, 30, 40, 50], какой индекс родителя узла в индексе 4?
В куче на основе массива, какой индекс левого ребёнка узла в индексе 2?
Который из этих массивов НЕ является валидной мин-кучей?
Почему полное двоичное дерево может быть сохранено в массиве без указателей?
▸lesson.inset.undefined
Почему структура кучи важна. Многим реальным системам нужно повторно извлекать минимальный (или максимальный) элемент — планирование задач, алгоритм Дейкстры, поиск медианы. Куча — это структура данных, которая делает это эффективно. Никакого поиска, никакой переупорядочивания. Просто O(1) для просмотра и O(log n) для добавления или удаления (операции, которые мы охватываем на следующем уроке). Форма полного двоичного дерева гарантирует, что дерево всегда сбалансировано, и кодирование массива экономит пространство и улучшает локальность кеша.
▸lesson.inset.undefined
Путаница между полным и заполненным. Заполненное двоичное дерево — это дерево, где каждый узел имеет 0 или 2 ребёнка (нет узла с одним ребёнком). Полное двоичное дерево имеет все уровни заполненные, кроме возможно последнего, заполненного слева направо. Куча — полная, не обязательно заполненная.
▸lesson.inset.undefined
Куча с 1 узлом. Куча с одним узлом валидна: это полное двоичное дерево (просто корень) и тривиально удовлетворяет свойству кучи (корень не имеет детей, чтобы нарушить его). Корень — и минимум, и максимум.
Объясни, почему куча может быть сохранена в массиве без указателей, и как вы бы нашли родителя узла в индексе i.
Куча — это двоичное дерево с двумя свойствами: оно полное двоичное дерево (все уровни полны, кроме возможно последнего, заполненного слева направо), и оно удовлетворяет свойству кучи (каждый родитель ≤ дети в мин-куче, или ≥ в макс-куче). Корень всегда является минимумом (мин-куча) или максимумом (макс-куча). Благодаря её полной форме, куча может быть сохранена в массиве без указателей: для узла с индексом i родитель находится в ⌊(i−1)∕2⌋, левый ребёнок в 2i+1 и правый ребёнок в 2i+2. Это кодирование экономит пространство и даёт O(1) доступ к корню. Структура гарантирует, что дерево всегда сбалансировано. Дальше: Раздел 08, урок 02 охватывает операции — push, pop и sift — которые сохраняют свойство кучи при изменении данных. Теперь, когда встретишь массив, который называют «кучей», знаешь, что проверить: полна ли форма и выполняется ли свойство порядка на каждой паре родитель–ребёнок?
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.