昇順および降順ヒープポート

Question

昇順ソートと降順ソートのためにどのヒープを構築するか。 ソート（昇順または降順）にヒープ（最大または最小）を使用できるかどうかを説明してください。

Answer 1

通常、昇順ソートには最大ヒープを使用し、降順ソートには最小ヒープを使用します。

これは、ヒープソートアルゴリズムが正常に記述されている方法に関係しています：

1. 元データ
2. と最大ヒープを構築今、最大の要素は、ツリーのルートにあり、取りますこの要素をツリーの最後の要素に切り替えます。
3. 新しいツリーを見てください。最後の位置は無視されています（これは既にソートされています）。新しいツリーは、もはや最大ヒープではないかもしれないので、ルートを下にずらして1つに変換します。
4. 手順2に進み、ツリーが空になるまで繰り返します。

あなたは、次のグラフィックでの作業におけるアルゴリズム見ることができます：あなたは私たちは、最大（最初の最大数を、置く各ステップで見ることができるように（Gmsによって作成された）

を2番目に大きい数字、...）が配列の最後にあり、それらは優位にソートされてしまいます。

もちろん、最大ヒープを使用して降順ソートを生成することもできます。見つかった最大値を新しい配列に入れるだけです。 （または、最後にソートされた配列を反転するだけです）