Нужна помощь с результатом простой левой вставки кучи

Question

Нужна помощь с результатом простой левой вставки кучи

У меня есть (мин) левая куча, как показано ниже:

               1
            /     \
            8      6
          /   \   /  \
         10   12 14   16
                 /\   /
               18 20  22

И меня просят показать результат вставки 21. Мое понимание левых куч - то, что вставка - это просто слияние одного узла, и в этом случае 21 должен сравниваться с каждым правым родителем, пока не достигнет NULL дочернего элемента 16, и должен просто автоматически попасть туда. Я ошибся? Должен ли он пойти куда-нибудь еще?

1

c++ binary-tree heap min-heap leftist-tree

Источник

user1687406 04 ноя '13 в 22:40

1 ответ

Другие вопросы по тегам c++ binary-tree heap min-heap leftist-tree

user1687406 06 ноя '13 в 04:39 2013-11-06 04:39 · Answer 1 · 2013-11-06 04:39

Я понятия не имею, почему комментаторы были так обеспокоены упорядочением узлов. Может, они не знали, что такое левая куча?

Оказывается, ответ заключается в том, что он становится правым ребенком 16 лет, но поскольку NPL 6 становится 2, что больше, чем NPL левого дерева, равное 1, вы должны поменять местами 8 и 6 деревьев.