binary-heap - ヒープのデータ構造

Question

たとえば、max-heap で n 番目に大きいキーの位置の下限を考えようとしています。ヒープが配列に配置されていると仮定します。上限の min(2^n-2, array size -1) だと思いますが、下限は常に 0 ですか?

Answer 1

問題の最初の調査では、n と下限および上限の間の次の関係が明らかになりました (ヒープに 14 の要素があると仮定)。

n   lb  up
1   1   1
2   2   3
3   2   7
4   2   14
9   3   14
10  4   14
12  5   14
13  6   14
14  8   14

ヒープ配列の特定の場所にある要素よりも大きくなる可能性のある要素の数を判断するには、その場所をルートとするサブツリーのサイズを計算します。これらの 2 つの数値は、式によって関連付けられます。

# of elements possible larger  = total number of elements - size of subtree - 1 

編集: 計算は逆方向に実行されることに注意してください。配列/ヒープ内の位置を指定すると、ヒープがソートされた場合に値がどの位置になるかを判断できます。ノードが与えられると、ヒープは 3 つのパーティションに分割できます。

1. 現在の要素よりも大きいことが保証されている要素 (親、親、親など)
2. 現在の要素 (現在の要素をルートとするサブツリー) よりも小さいことが保証されている要素
3. 残りの要素は、現在の要素より大きくても小さくてもかまいません。

14 個の要素を持つヒープの例を見て、6 番目の場所で可能な値の範囲を決定したい場合、グループは次のようになります。

• グループ 1 には 2 つの要素 (3, 1) が含まれます
• グループ 2 には 2 つの要素 (12、13) が含まれます
• グループ 3 には、残りの 9 つの要素 (現在の値を除く) (2、4、5、7、8、9、10、11、14) が含まれます。

したがって、下限は 3 (グループ 1 の要素数 + 1) であり、上限は 11 (グループ 1 の要素数 + グループ 3 の要素数 + 1) です。