Двоичная куча - найти количество узлов на высоте

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

Проблема в:

Для двоичной кучи с 1492 узлами число узлов высоты два равно _187_.

Я понимаю, что с 1492 узлами бинарная куча имеет глубину log (1492)/log (2) = 10, высоту два должно иметь 2 ^ (10-2) узлов, что должно быть 256

Почему ответ 187?

Спасибо


person Lex L    schedule 20.03.2014    source источник
comment
С 1492 узлами это не полное двоичное дерево.   -  person timrau    schedule 20.03.2014
comment
так что 256 - 187 = 69, что означает, что 69 отсутствуют на этой высоте. Как рассчитать количество недостающих узлов на высоте?   -  person Lex L    schedule 20.03.2014


Ответы (1)


В случае, если кому-то нужно знать. Я узнал, что формула n / 2 ^ (ч + 1), поэтому 1492 / 2 ^ (2 + 1) = 186,5.

person Lex L    schedule 21.03.2014