Каковы минимальные и максимальные числа элементов в куче высоты H?

Question

Я наткнулся на вопрос:

Каковы минимальные и максимальные числа элементов в куче высоты $ h $ ?

к которому я придумал эту теорию: $$ \ sum_ {i= 0} ^ {h-1} 2 ^ i= 2 ^ h-1 $$

$ 2 ^ h-1 $ - это внутренние узлы, и это понимается в соответствии с понятым фактом. Но потому что ниоткуда, кроме CLRS, упоминает кучи, чтобы быть <сильным> почти полным двоичным деревом везде, где он упоминается как полное двоичное дерево.

Максимальное количество элементов может быть легко вычислено: $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {h + 1} -1 $$

Но я не могу получить точку вычисления минимального количества элементов: Должно быть: $$ 2 ^ {h} +1 $$ для $ 0 $ или $ 2 $ Детская собственность

или должен быть: $$ 2 ^ {h} $$ для $ 0 $ или $ 1 $ Детская собственность

Ссылка1: https://walkccc.github.io/clrs/ CHAP06 / 6.1 / # 61-1

Ссылка2: Heapsort

Спасибо.

Answer 1

Куча высоты $ h $ завершено до уровня на глубине $ H-1 $ И должен иметь хотя бы один узел на уровне $ h $ .

Поэтому минимальное общее количество узлов должно быть, по меньшей мере, $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ ч. $ , и это тесно, поскольку куча с 2 $ ^ h $ Узлы имеют высоту $ H $ .