Каковы минимальные и максимальные числа элементов в куче высоты H?
-
29-09-2020 - |
Вопрос
Я наткнулся на вопрос:
Каковы минимальные и максимальные числа элементов в куче высоты $ 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
Спасибо.
Решение
Куча высоты $ h $ завершено до уровня на глубине $ H-1 $ И должен иметь хотя бы один узел на уровне $ h $ .
Поэтому минимальное общее количество узлов должно быть, по меньшей мере, $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ ч. $ , и это тесно, поскольку куча с 2 $ ^ h $ Узлы имеют высоту $ H $ .