特定のレベルの二項ヒープのノード数を数える

Question

私たちは2016個のノードからなる二項ヒープを持っています。

ヒープノード6 strees 512 256 128 64 32および16

から構成しかし、どのように、我々は、特定のレベル内のノードの数を計算することができますか？我々は

11111100000 

を得るバイナリにDecompositing数を計算するための公式とはどのようなノードですか？たとえば3レベルですか？

これは究極の解決策ですか？おかげ

Answer 1

用語「二項ツリーは、」n次の二項ツリーで、そこに正確には、n-そのレベルの二項ツリー内のk個のノードを選択し、任意の整数に≤ K ≤ nは0を与えているという事実から来ています。あなたの質問に記載されているように、問題の番号のバイナリ表現を使用して、2項ヒープ内に存在するツリーを決定することができます。結果として、nを計算する高速な方法がある場合（ルックアップテーブルまたは他の方法を使用して）、kを選択すると、nに設定された1ビットを見て、バイナリヒープのレベルkにあるノードの数を判断できます各セット1ビットに対して、その個々のツリー内のノードの数を計算し、その結果を合計する。