人生初心者の雑記

すべてにおいてド素人な人がいろんなことを書くよ

N分ヒープの要素Xの左の子がN(X-1)+2になる

N分ヒープを1から始まる配列の番号にわりあてたとき、

番号x の左の子は 番号 N(x-1)+2

ってのを示すメモ



根から深度を1,2,...dて数えるとする

深度dの右端の番号は,深度dには N^(d-1)個 の要素があるので、等比の和で 
R(d) = (N^d-1)/(N-1)

深度dの左端の番号は,深度d-1の右端の番号+1 なので
L(d) = R(d-1)+1
= (N^(d-1)-1)/(N-1) + 1



要素xが深度dにあるとする

要素xの左にある深度dのノードは、x - L(d) 個 ある

要素xのもつ一番左の子の左側には,深度d+1のノードが N*(x - L(d)) 個 ある (N分だから。)


よってxのもつ一番左の子の番号は
(深度d+1の一番左端の要素の番号) + (xのもつ一番左の子の左側にあるノードの数)

ℓ(x) = L(d+1) + N*(x-L(d))

= (N^d - 1)/(N-1) +1 + Nx - N(N^(d-1)-1)/(N-1) - N

= N(x-1)+2

余談: 番号xのある深度の求め方
xの深度がdにあるとする

{
R(d-1) < x <= R(d)
}

R(d),L(d) は上の方で書いたのとおなじ

(N^(d-1)-1)/(N-1) < x <= (N^d-1)/(N-1)
N^(d-1) < x(N-1) + 1 <= N^d (↑の全辺にN-1をかけてから1をたす)
1/N < (x(N-1)+1)/N^d <= 1 (↑の全辺をN^dでわる)
(x(N-1)+1) <= N^d < N(x(N-1)+1) (↑の全辺の逆数を取ったあと(x(N-1)+1)をかける)

ここで、全辺の{log_{N}}をとる

{
log_{N}(x(N-1)+1)< d <= log_{N}(N(x(N-1)+1)) = 1 + log_{N}(x(N-1)+1)
}

ここで

{
k = log_{N}(x(N-1)+1)
}

とすると

{
 k < d <=  1 + k
}

符号をかえて

{
 -k-1 <= -d <  - k
}

ここで、整数 a と 実数 b において

{
 a = [b]\\
\Leftrightarrow b-1 < a <= b
}

がなりたつので

{
 -d = [-k]\\
\Leftrightarrow d = -[-k]\\
\Leftrightarrow d = -[-log_{N}(x(N-1)+1)]
}

番号xのある深度は
{
 -[-log_{N}(x(N-1)+1)]
}