특정 수준의 이항 힙의 노드 수를 계산합니다.

Question

우리는 2016 개의 노드로 구성된 이항 힙을 가지고 있습니다.

우리가

가

11111100000 

힙 노드 512 256 128 64 32 16

하지만 어떻게 우리가 일정 수준에있는 노드의 수를 계산할 수와 6 strees 구성 얻을 바이너리로 Decompositing? 수를 계산하기위한 공식은 무엇이며 어떤 노드가 예를 들어 3 단계입니까?

이 문제가 궁극적 인 해결책입니까? 감사

Answer 1

"이항 트리"라는 용어는 임의의 정수 0 ≤k ≤ n이 주어진 n 차수의 이항 트리에서 그 레벨의 이항 트리에서 정확히 n 개의 k 노드를 선택한다는 사실에서 비롯됩니다. 귀하의 질문에 언급했듯이 문제의 번호를 이진 표현으로 사용하여 이항 힙에 존재하는 나무를 결정할 수 있습니다. 결과적으로, 당신이 n을 계산하는 빠른 방법을 가지고 있다면 (룩업 테이블이나 다른 방법을 사용하여) k를 선택하면, n에 설정된 한 비트를보고 이항 힙의 레벨 k에있는 노드의 수를 결정할 수 있습니다 각각의 1 비트 세트에 대해, 그 개별 트리 내의 노드들의 수를 계산하고, 그 결과를 합산하는 단계를 포함한다.