@Carver182
инженер-программист

Как происходит восстановление binary heap (бинарной кучи)(метод heapify)?

Загвоздка возникла когда родитель оказался меньше обоих своих потомков. В какую сторону его спускать, в сторону большего или меньшего потомка? На разных сайтах пишут по разному, на хабре и на вики пишут что в сторону наибольшего потомка, на нескольких других что в сторону меньшего из двух, а где-то, вообще, написали в сторону меньшего/большего, где-то просто в левое поддерево. Решил сам построить дерево на основе числовой последовательности. Сделал из нее просто бинарное дерево а потом с помощью функции heapify(с уходом в строну бОльшего потомка) превратил ее в кучу и для проверки правильности, тоже самое, только путем поочередного добавления каждого узла. Результаты не совпали. Помогите разобраться, как должен работать алгоритм, а?
Последовательность: 9-11-3-6-14-10-11-11-7-12-11-4

С помощью функции heapify:
14
/ \
12 11
/ \ / \
11 11 10 3
/ \ / \ /
6 7 9 11 4

C помощью поочередного добавления каждого узла:
14
/ \
12 11
/ \ / \
11 11 4 10
/ \ / \ /
6 7 9 11 3
  • Вопрос задан
  • 259 просмотров
Решения вопроса 1
SagePtr
@SagePtr
Еда - это святое
В зависимости от того, в каком порядке эта куча должна быть слабо отсортирована. Если на вершине должен находиться элемент с максимальным значением ключа - то спускать элемент в сторону большего, если с минимальным - в сторону меньшего.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы