Нужна помощь с результатом простой левой вставки кучи
У меня есть (мин) левая куча, как показано ниже:
1
/ \
8 6
/ \ / \
10 12 14 16
/\ /
18 20 22
И меня просят показать результат вставки 21. Мое понимание левых куч — то, что вставка — это просто слияние одного узла, и в этом случае 21 должен сравниваться с каждым правым родителем, пока не достигнет NULL-потомка 16, и должен просто автоматически попасть туда. Я ошибся? Должен ли он пойти куда-нибудь еще?
Решение
Я понятия не имею, почему комментаторы были так обеспокоены упорядочением узлов. Может быть, они не знали, что такое левая куча?
Оказывается, ответ заключается в том, что он становится правым потомком 16 лет, но поскольку NPL 6 становится 2, что больше, чем NPL левого дерева, равное 1, вы должны поменять местами 8 и 6 деревьев.
Другие решения
Других решений пока нет …