ヒープソートが安定しない理由を理解しようとしています。これをグーグルで検索しましたが、直感的で適切な説明が見つかりませんでした。
安定した並べ替えの重要性を理解しています。これにより、複数のキーに基づいて並べ替えることができ、非常に有益です (つまり、それぞれが異なるキーに基づいて複数の並べ替えを行うことができます。すべての並べ替えは要素の相対的な順序を保持するため、以前の並べ替えを合計すると、複数の基準で並べ替えられた要素の最終的なリストが得られます)。しかし、なぜヒープソートもこれを保持しないのでしょうか?
ご協力いただきありがとうございます！
ヒープソートが不安定な例
配列を検討21 20a 20b 12 11 8 7してください (既に max-heap 形式になっています)
ここ20a = 20bでは、それらを表す順序を区別するためだけに20a、20b
ヒープソートが最初21に削除され、最後のインデックスに配置された後、削除され、最後から 2 つ前の20aインデックスと20b最後から 2 つ前のインデックスに配置されるため、ヒープソート後、配列は次のようになります。
7 8 11 12 20b 20a 21.
要素の順序を保持しないため、安定しません
heapsort からの結果の最終シーケンスは、(キー フィールドに基づいて) 純粋にサイズ順で作成されたヒープからアイテムを削除することから得られます。
元の順序での項目の順序に関する情報は、最初に行われたヒープ作成段階で失われました。
サイズ n (任意の値) の配列を取り、ヒープに 2 つの連続した要素 (15 と仮定) があり、それらの親インデックスが 4 や 20 のような値を持つ場合 (これが実際の順序 (....4,20) ,.....,15,15.....). 4 と最初の 15 の相対的な順序は同じままですが、20>15 の場合、ヒープ ソート アルゴリズムで定義されているように、2 番目の 15 が前面 (スワップ) になります。相対的な順序はなくなりました。