Постановка задачи :

Вам дан массив «ARR» целых чисел, содержащий «N» элементов. Ваша задача — преобразовать входной массив в min-Binary Heap.

Минимальная двоичная куча — это полное двоичное дерево, в котором значение каждого внутреннего узла меньше или равно значениям дочерних элементов этого узла.

Первая строка каждого теста содержит целое число «N», обозначающее количество элементов в массиве «ARR».

Вторая строка каждого набора входных данных содержит N целых чисел, разделенных пробелом, обозначающих элементы массива.

Для каждого тестового случая программа проверки будет печатать 1, если возвращаемый массив представляет допустимую минимальную кучу. В противном случае программа проверки выдаст 0.

Пример ввода:

5
1 3 5 4 6

Пример вывода:

1

Объяснение примера тестового примера:

Одним из возможных представлений входного массива с минимальной кучей является массив [ 1, 3, 5, 4, 6 ], который совпадает с входным массивом.

Подход :

Идея состоит в том, чтобы следовать нисходящему подходу. Данный массив не обязательно представляет собой кучу. Чтобы преобразовать входной массив в кучу, мы будем кучи полного двоичного дерева, сформированного из массива, в обратном порядке, то есть от самого правого элемента к самому левому элементу. Heapify определяется как процесс преобразования двоичного дерева в структуру данных Heap. Нам не нужно накапливать листовые узлы, поскольку они уже загружены, потому что у них нет ни левого, ни правого потомка. Обратите внимание, что представление входного массива полного бинарного дерева обозначает обход дерева по порядку уровней. Нам нужно найти позицию первого нелистового узла справа и выполнить операцию heapify для каждого узла в обратном порядке уровней.

Heapify — это процесс преобразования двоичного дерева в структуру данных Heap. Алгоритм heapify — это рекурсивный алгоритм, который используется для увеличения узла, предполагая, что оба поддерева узла уже загружены. На каждом шаге кучи мы проверяем, имеет ли текущий узел значение меньше, чем оба его дочерних элемента (если они существуют). Если да, то узел и узлы в соответствующем ему поддереве уже находятся в куче. В противном случае мы меняем узел на дочерний, имеющий меньшее значение, и рекурсивно вызываем функцию heapify для этого дочернего элемента, поскольку поддерево было изменено, и теперь нам придется снова его кучить. Рекурсивный алгоритм останавливается, если поддерево уже заполнено.

Временная сложность: O(N)
Пространственная сложность: O(log N)

Код :

Спасибо за чтение

Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.

Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.