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

Question

У нас есть биноминальная куча, состоящая из 2016 узлов.

Декомпозируя в двоичный файл, мы получаем

11111100000

Куча состоит из 6 веток с узлами 512 256 128 64 32 и 16.

Но как мы можем рассчитать количество узлов на определенном уровне? Какова формула для вычисления числа и какого узла, например, на 3 уровне?

Есть ли какое-либо окончательное решение для этого? Спасибо

Answer 1

Термин "биномиальное дерево" происходит от того факта, что в биномиальном дереве порядка n при любом целом числе 0 ≤ k ≤ n в этом биномиальном дереве ровно n выбирается k узлов. Как вы отметили в своем вопросе, вы можете определить, какие деревья будут присутствовать в биноминальной куче, используя двоичное представление рассматриваемого числа. В результате, если у вас есть быстрый способ вычисления n, выберите k (используя таблицу поиска или какой-либо другой метод), вы можете определить, сколько узлов находятся на уровне k в биномиальной куче, просмотрев один бит, установленный в n и для каждого набора 1 бит вычисляют количество узлов в этом отдельном дереве, затем суммируют результат вместе.