Как происходит восстановление 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
В зависимости от того, в каком порядке эта куча должна быть слабо отсортирована. Если на вершине должен находиться элемент с максимальным значением ключа - то спускать элемент в сторону большего, если с минимальным - в сторону меньшего.
Артур: потому что у вас есть одинаковые элементы в куче. Попробуйте с различными элементами. А для одинаковых (если нужно топить вершину, а оба потомка одинаковы) - можно как влево сдвинуть, так и вправо, от этого куча не перестанет быть двоичной кучей, но внутри её распределение может быть различно из-за этого. Это ни на что не влияет.
SagePtr: т.е. результат может быть неоднозначным? В моем случае, результат начал разниться в тот момент когда родитель был с ключом =3, а потомок слева=10, справа =11(они же не одинаковые?). По логике надо было топить вправо. Но если топить влево результат как-раз совпал бы.
Артур: да, результат может быть неоднозначным, главное, чтобы выполнялось требование двоичной кучи - любой элемент должен быть не меньше его потомков.
В примере с 3, 10, 11 - нужно в любом случае топить в сторону 11.
Добавил вручную на листке бумаги эти 12 элементов - получилось такое же дерево, как у вас во втором примере. При добавлении вершин в пустое дерево, добавляя их в конец и производя всплытие вверх - результат будет однозначным. Но если вы уже построили другое бинарное дерево и пытаетесь превратить его в кучу - тут уже зависит от того, какой именно алгоритм для этой цели используется (в каком порядке он сравнивает, топит или всплывает элементы), и какое именно бинарное дерево вы изначально построили, потому что одни и те же элементы можно превратить в двоичную кучу различными способами.
11 3 10 и 11 10 3 - это обе двоичные кучи и обе правильные.
Артур: собственно, вот здесь всё расписано: https://habrahabr.ru/post/112222/
В подпункте "Построение двоичной кучи" описаны два способа построения, проверил их - получил как раз оба ваших результата.
SagePtr: В целом, стало ясно. Неоднозначный результат может быть из-за того что из одного и того же набора чисел можно собрать разные binary tree и, соответственно, получаться разные кучи. А как понять "в каком порядке он сравнивает, топит или всплывает элементы"? Я полагал, раз мы топим родителя, то потомок всплывет на его место, иначе никак, верно? А сравниваем узлы порядку, по возрастанию индексов, тоже, иначе никак же?
Простой