8.5 演習¶

8.5.1 確認問題¶

配列 [9, 7, 8, 3, 5] は最大ヒープを表しています。ここに 10 を追加します。

解答

10 を追加した後のインデックスは 5 で、その親ノードのインデックスは \(\lfloor(5-1)/2\rfloor=2\) です。親ノードの値は 8 です。
10 は 8 より大きいため、1 回目の交換後は [9, 7, 10, 3, 5, 8] です。 10 は親ノードの 9 よりも大きいため、2 回目の交換後は [10, 7, 9, 3, 5, 8] です。これで 10 が根ノードに到達したため、ヒープ化は終了します。
最終的なヒープ頂点は 10 で、交換回数は 2 回です。

配列 [1, 4, 3, 7, 6, 2] は完全二分木を表しています。最小ヒープでは、すべての親ノードがその子ノード以下でなければなりません。インデックス \(i\) に対して、左右の子ノードのインデックスはそれぞれ \(2i+1\) と \(2i+2\) です。

インデックス 2 の子ノードのインデックスと値は、それぞれいくつですか？
インデックス 2 にあるノードの値は 3 です。子ノードとの間で最小ヒープの条件に反していますか？反している場合、どの 2 要素を交換しますか？
問い 2 の判断に基づき、条件に反している場合は交換後の配列を書き、反していない場合は交換が不要な理由を説明してください。最後に、ほかの親子関係も確認してください。

解答

インデックス 2 の左子ノードはインデックス 5、値は 2 です。右子ノードのインデックスは 6 ですが、配列の長さは 6 なので、右子ノードは存在しません。
親ノードの値 3 は子ノードの値 2 より大きく、最小ヒープの条件に反しています。そのため、インデックス 2 とインデックス 5 の要素を交換します。
交換後の配列は [1, 4, 2, 7, 6, 3] です。順に確認すると、 1 ≤ 4、1 ≤ 2、4 ≤ 7、4 ≤ 6、2 ≤ 3 です。すべての親ノードがその子ノード以下なので、現在は最小ヒープの条件を満たしています。

データストリーム [4, 1, 7, 3, 8] から最大の 3 つの数を保持するために、大きさが 3 以下の最小ヒープを管理します。

まず、最初の 3 つの数を順に最小ヒープへ入れます。ヒープが満杯になった後は、新しい数を 1 つ読み込むたびに、その数がヒープ頂点より大きければヒープ頂点を削除して新しい数を入れ、そうでなければヒープを変更しません。

各数を読み込んだ後、ヒープに保持されている数とヒープ頂点を書いてください。保持されている数は集合として書けばよく、ヒープ配列内での並びを書く必要はありません。

解答

各数を読み込んだ後の結果は、次のとおりです。

ヒープが満杯になった後、ヒープ頂点は、現在保持している数のうち最も小さい数です。新しい数がヒープ頂点より大きい場合に限り、ヒープ頂点を新しい数に置き換えます。最終的に保持される {4, 7, 8} は、まさに最大の 3 つの数です。

整数配列 nums と整数 \(k\) が与えられます。ここで \(1 \le k \le n\) で、\(n\) は配列の長さです。配列を大きい順に並べたとき、\(k\) 番目にある要素を返してください。

重複する要素は別々に数えます。たとえば、[5, 5, 2] で 2 番目に大きい要素も 5 です。大きさが \(k\) 以下の最小ヒープを使って求めてください。

解法のヒント