Часть 7 из серии «Структура данных с JavaScript».
В этой статье мы рассмотрим другой тип структуры данных — двоичные кучи. Если вы не знакомы с деревьями, я рекомендую сначала ознакомиться со статьей ниже.
MaxBinaryHeap против MinBinaryHeap
Двоичная куча — это тип двоичного дерева с дополнительными правилами. Для быстрого просмотра; бинарное дерево — это структура данных, состоящая из узлов с родственными и дочерними отношениями. Каждый родительский узел может иметь не более двух дочерних узлов. В двоичной куче есть два дополнительных правила:
- Все уровни дерева должны быть заполнены по порядку. Если последний уровень дерева не заполнен, узлы дерева заполняются слева направо.
2. Есть два способа хранения данных в дереве:
- MaxBinaryHeap — Родительское значение должно быть больше дочерних значений. На изображении ниже показана максимальная двоичная куча. Как видите, корневое значение равно 100, а каждый дочерний элемент (19 и 36) меньше родительского значения. Мы можем сделать ту же проверку для каждого узла в дереве. Порядок левых или правых свойств не имеет значения, пока дочерние элементы меньше родительского.
- MinBinaryHeap —Родительское значение должно быть меньше дочерних значений. На изображении ниже показана минимальная двоичная куча. Корневое значение равно 1, и каждый дочерний узел (2 и 3) больше родительского узла. То же самое относится к каждому значению в дереве. Порядок левых или правых свойств не имеет значения, пока дочерние элементы больше, чем родительские.
Использование массива для представления кучи
Самый простой способ хранения двоичной кучи — использование массива. Здесь задействована некоторая математика, но не волнуйтесь; Как только мы поймем основные уравнения, использовать их будет просто.
Чтобы найти дочерние элементы любого родителя (n), мы будем использовать следующие уравнения:
- Левый дочерний узел: (2 * n) + 1
- Правый дочерний узел: (2 * n) + 2
Чтобы найти родительский узел любого дочернего элемента (n), мы будем использовать следующее уравнение:
- Родительский узел: Math.floor((n - 1)/2)
Давайте посмотрим на изображение выше, на котором показана максимальная двоичная куча. Мы можем использовать наши уравнения для представления нашей двоичной кучи в виде массива. [100, 19, 36, 17, 12, 25, 5, 9, 15, 6, 11, 13, 8, 1, 4]
Например, наше корневое значение 100 хранится в нашем массиве с индексом 0. Мы можем найти двух дочерних элементов, 19 и 36, в массиве с индексами 1 и 2, используя наши уравнения.
Левый дочерний узел: (2 * 0) + 1 = 1
Правый дочерний узел: (2 * 0) + 2 = 2
Затем, если мы можем взглянуть на 19 как на родительское значение, мы увидим, что 19 имеет двух дочерних элементов, 17 и 12. Используя наши уравнения, мы увидим, что эти два узла находятся в массиве с индексами 3 и 4.
Левый дочерний узел: (2 * 1) + 1 = 3
Правый дочерний узел: (2 * 1) + 2 = 4
Если мы хотим найти родителя любого узла, мы можем использовать наше другое уравнение, Math.floor((n - 1)/2). Например, давайте посмотрим на значение 12, хранящееся в индексе 4. Родителем является значение 19, которое хранится в индексе 1.
Математический пол ((4 - 1) / 2) = Математический пол (1,5) = 1
Создание нашего класса двоичной кучи
В нашем примере ниже мы будем создавать максимальную двоичную кучу. Как только вы поймете, как это построить, создание минимальной двоичной кучи можно будет сделать аналогичным образом. Для начала мы создадим класс и назовем его MaxBinaryHeap. У него будет одно свойство, называемое values, которое будет инициализировано как пустой массив.
class MaxBinaryHeap {
constructor() {
this.values = [];
}
}
Вставка в нашу двоичную кучу
Давайте сначала посмотрим, как мы можем добавить значения в нашу максимальную двоичную кучу. Первым шагом будет поместить значение в конец нашего массива значений. Метод push поместит значение в следующее место в нашей куче. Помните первое правило нашей кучи: Все уровни дерева должны быть заполнены по порядку. Если последний уровень дерева не заполнен, узлы дерева заполняются слева направо.
Затем нам нужно будет сделать эффект пузырьков. Это означает, что мы будем сравнивать вставленное значение с родительским значением. Если вставленное значение больше, чем у родителя, мы поменяем эти значения. Мы будем продолжать это до тех пор, пока наше вставленное значение не окажется в правильном месте.
Удаление из нашей двоичной кучи
При удалении из двоичной кучи мы обычно удаляем корневое значение. Это означает, что в двоичной куче max мы удаляем наибольшее значение, а в двоичной куче min мы удаляем наименьшее значение. В нашем примере мы будем вызывать наш метод, extractMax.
Для этого мы сначала поменяем корневое значение на последнее значение в нашем массиве. Затем мы создадим эффект пузыря вниз. Поскольку наш новый корень, скорее всего, не будет в правильном положении, мы сравним это значение с его дочерними элементами. Какой бы потомок ни был больше, мы поменяем его местами с родителем. Мы будем продолжать делать это, пока значение не окажется в правильном месте. В конце концов, мы вернем максимальное значение.
Подведение итогов
Спасибо за чтение! Надеюсь, теперь у вас есть представление о двоичных кучах и о том, как вставлять и удалять из максимальной двоичной кучи. Если вы хотите реализовать это для минимальной двоичной кучи, все, что вам нужно сделать, это изменить несколько операторов и несколько строк кода.
Двоичные кучи могут быть полезны для сортировки и реализации других структур данных, как мы увидим в следующей части серии, где мы рассмотрим приоритетные очереди. С точки зрения нотации Big O, двоичные кучи лучше всего подходят для вставки и удаления. Оба имеют большой O из O (log N).
Хотите продолжить обучение? Ознакомьтесь с этой статьей ниже о поиске в глубину и поиске в ширину.
