Общий вопрос о куче и ее структуре

Question

Скажем, у вас есть [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] в вашей куче. Вы бы 12 в качестве верхнего родителя. Будут ли 11 и 10 единственными детьми 12 лет, потому что они самые высокие из них?

Звучит очевидно, но мой код выглядит правильно, и я получаю противоречивые результаты. Вместо 11 и 10, как детей от 12, я получаю 11 и 7. У обоих 11 и 7 есть потомки меньших значений, чем у них, поэтому мой код не хочет продолжать их сортировать.

Мой главный вопрос: может ли 7 быть ребенком 12 лет, если дети 7 имеют меньшее значение?

Answer 1

Да, 7 может быть правым потомком корня в дереве кучи, сохраняя последовательность целых чисел от 1 до 12 (включительно). Рассмотрим следующий линейный массив, представляющий это дерево с обычной зависимостью между позицией узла и позициями его дочерних элементов:

V = [12, 11, 7, 10, 9, 3, 2, 8, 6, 5, 4, 1]

Свойство Heap действительно дляэтот массив, причина для всех i в диапазоне [0, 6]:

V[i] > V[2*i + 1]
V[i] > V[2*i + 2]