Алгоритмы с нуля
Куча
Вы знаете, что деревья имеют форму. Теперь представьте дерево, сформированное так компактно, что вы можете сохранить его в массиве вообще без указателей. И представьте дерево, сделанное так, что корень всегда является наименьшим (или наибольшим) элементом. Никакого поиска, никаких сравнений — он прямо там на индексе 0. Это куча. Она объединяет две идеи: определённую форму (полное двоичное дерево) и определённое правило упорядочения (свойство кучи). Вместе они дают 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).
Построение кучи с нуля
Построим мин-кучу вручную и сохраним её в массиве:
1
// Мин-куча сохранена как массив
2
const minHeap = [1, 3, 2, 5, 4];
3
4
// Вспомогательные функции для арифметики индексов
5
function parentIndex(i) {
6
return Math.floor((i - 1) / 2);
7
}
8
9
function leftChildIndex(i) {
10
return 2 * i + 1;
11
}
12
13
function rightChildIndex(i) {
14
return 2 * i + 2;
15
}
16
17
// Доступ к корню (минимум в мин-куче)
18
console.log("Корень (минимум):", minHeap[0]); // 1
19
20
// Доступ к детям индекса 1 (значение 3)
21
console.log("Значение в индексе 1:", minHeap[1]); // 3
22
console.log("Левый ребёнок индекса 1:", minHeap[leftChildIndex(1)]); // 5
23
console.log("Правый ребёнок индекса 1:", minHeap[rightChildIndex(1)]); // 4
24
25
// Доступ к родителю индекса 3 (значение 5)
26
console.log("Значение в индексе 3:", minHeap[3]); // 5
27
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 узлами. Максимум всегда в корне.
1
// Макс-куча сохранена как массив
2
const maxHeap = [50, 30, 20, 10, 15, 8, 5, 2, 3, 7];
3
4
function parentIndex(i) {
5
return Math.floor((i - 1) / 2);
6
}
7
8
function leftChildIndex(i) {
9
return 2 * i + 1;
10
}
11
12
function rightChildIndex(i) {
13
return 2 * i + 2;
14
}
15
16
// Проверьте свойство кучи: родитель >= дети
17
for (let i = 0; i < maxHeap.length; i++) {
18
const left = leftChildIndex(i);
19
const right = rightChildIndex(i);
20
21
if (left < maxHeap.length) {
22
console.log(`Родитель ${maxHeap[i]} >= левый ребёнок ${maxHeap[left]}: ${maxHeap[i] >= maxHeap[left]}`);
23
}
24
if (right < maxHeap.length) {
25
console.log(`Родитель ${maxHeap[i]} >= правый ребёнок ${maxHeap[right]}: ${maxHeap[i] >= maxHeap[right]}`);
26
}
27
}
- L2 Макс-куча: каждый родитель >= его дети.
- L16 Цикл через каждый узел.
- L17 Вычислите индексы левого и правого детей.
- L20 Если левый ребёнок существует, проверьте свойство кучи.
- L23 Если правый ребёнок существует, проверьте, что родитель >= ребёнок.
1
const minHeap = [1, 3, 2, 5, 4];
2
// Навигация от корня к узлу в индексе 3
3
let current = 0; // Начните с корня
4
let target = 3; // Индекс 3 имеет значение 5
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 — которые сохраняют свойство кучи при изменении данных.