Снизу вверх строительные кучи

Question

Я работаю над вопросом, где у меня есть 10 ключей, и я должен сделать конструкцию снизу вверх. Согласно моей книге, я должен построить (n + 1) / 2 кучи, что составляет 11/2 = 5,5 кучи для дна. Затем 11/4 для 2-го уровня, 11/8 для 3-го и т. Д.

Проблема в том, что я получаю это в результате:

(например, используя 'a')

Так как 11/2 = 5,5, поэтому я округляю до 6, 11/4 = 2,75, т. Е. 3, 11/8 = 1,375, т. 2, и 11/16 = 0,6875, т. Е. 1.

Даже если я не соберусь, у меня все еще есть странные кучи. Может кто-нибудь объяснить, где я испортил?

Answer 1

Вы запутались, потому что только последний слой в двоичной куче не может быть заполнен.Куча с 10 элементами должна выглядеть примерно так:

        1
     /     \
    2       3
   /  \    / \
  4    5  6   7
 /\   /
8  9  10

Что касается построения снизу вверх, вам не нужно слишком много думать о количестве куч.Основная идея заключается в том, что

1. Узлы без дочерних элементов являются тривиальными кучами.
2. Если узел имеет две кучки в качестве дочерних, мы можем преобразовать его в большую кучу с помощью операции всплытия.

Итак, в начале мы знаем, что узлы в 4-м слое (8, 9 и 10) уже являются кучами.Затем мы можем использовать это для наложения узлов в третьем слое, чтобы превратить их в кучи, и так далее.