Мы рассмотрели построение дерева min-heap из уже построенного дерева. Min-heap также может быть построен непосредственно из массива. Если мы посмотрим на массив, который мы использовали в статье Создание кучи из массива, мы увидим, насколько легко построить минимальную кучу из массива.
Начнем с добавления первого узла, 7.
Кучи строятся слева направо. Следующий добавляемый элемент - 2.
Поскольку мы создаем минимальную кучу, все дочерние узлы должны быть меньше родительского узла. Число 2 меньше, чем 7, поэтому два узла меняются местами.
Затем добавляется элемент 9. Поскольку 9 больше, чем 2, замена не требуется.
Далее добавляется элемент 4.
Поскольку 4 меньше 7, два узла меняются местами.
Затем элемент 4 сравнивается с элементом 2, чтобы убедиться, что он не меньше. Поскольку это не так, элементы остаются на своих текущих позициях. Затем добавляется элемент 5. Поскольку элемент 4 уже меньше элемента 5, узлы остаются на своих текущих позициях.
Наконец, добавлен элемент 3.
Поскольку элемент 3 меньше элемента 9, два узла меняются местами.
Элемент 3 также сравнивается с элементом 2. Поскольку элемент 3 больше, чем элемент 2, два узла остаются на своих текущих позициях. Нет дополнительных элементов массива. На этом построение дерева минимальной кучи завершено.
Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает эту структуру данных и многое другое.
