Высота кучи с n элементами

Question

У меня следующий вопрос:

"Высота дерева - это длина самой длинной ветви дерева. Как определить высоту, какова высота кучи с n элементами?Дайте четкое и точное объяснение с вашим ответом. "

Куча = двоичное дерево

Я знаю, что число полного двоичного дерева составляет 2 ^ (количество уровней - 1)

До сих пор я пробовал следующее:

Если существует три кучи (2 полных двоичных дерева и 1 неполное двоичное дерево), таких что:

• Куча A = равнаполное двоичное дерево высотой H
• куча B = - это двоичное дерево высоты с большим количеством узлов, чем A, но меньше чем C (поэтому имеет ту же высоту, что и C - я думаю?)
• Куча C = это двоичное дерево высотой H + 1

Я могу сказать, что высота B находится между высотой A и C, а количество элементов B находится между 2 ^ (n° уровней A - 1) и 2 ^ (n ° уровней C - 1).

Но я не уверен, как к тому, что высотат кучи с п элементов.

Answer 1

Как вы знаете, куча - это полное двоичное дерево.

Давайте рассмотрим некоторую кучу:

Мы видим, что:

• если куча имеет 1 узел, ее высота будет 1

• если куча имеет от 2 до 3 узлов, ее высота будет 2

• , если куча имеет от 4 до 7 узлов, ее высота будет 3

• ...

• если куча имеет от 2 ^ i до 2 ^ (i + 1) - 1 узел, его высота будет i

Обратите внимание, что высота кучи увеличивается только тогда, когда мы заполняем некоторый уровеньузлы и начать новый.

Это происходит только на узлах: 1, 2, 4, 8, 16, 32, ...

Таким образом, куча с n узлами будет иметь высоту пола(log2 (n)) + 1