algorithm - 最小ヒープを使用して k 番目に大きい要素を見つける

Question

最小ヒープを使用して k 番目に大きい要素を見つけることについて質問があります。アルゴリズムは次のとおりです。

1. 最初の k 要素を取り、最小ヒープを構築します

2. S の最小の要素を Sk とします。

3. 残りの nk 個の要素から、新しい要素を見てください。

4. 新しい要素が Sk よりも大きい場合は、S でそれを置き換え、ヒープを並べ替えます。

5. S は新しい最小要素を持つことになります。

6. 他のすべての要素を見た後、Skが答えです

このアルゴリズムがわかりません。たとえば、数値を 1、2、3、4 とします。4 番目に大きい 4 を見つけたいとします。しかし、アルゴリズムを使用する場合、最初の 4 つの要素を取得して最小ヒープを構築すると、Sk は 1 になります。

私は何を間違っていますか？誰かが助けてくれれば幸いです。ありがとう

Answer 1

あなたの混乱は用語にあると思います。シーケンス 1、2、3、4 の最大の要素は数値 4 です。2 番目に大きい要素は 3、3 番目に大きい要素は 2、4 番目に大きい要素は 1 です。アルゴリズムは 1 を返すため、正しく機能します。 .

ただし、4 はシーケンス内で k 番目に小さい要素です。k 番目に小さい要素を見つけたい場合は、最小ヒープを最大ヒープと交換し、アルゴリズムを適切に調整するだけです。

お役に立てれば！