- ふるい落とし中
- 比較中
- 交換済み
- 確定
ヒープソート
ヒープソートはリストを二分木として読み、最大ヒープに並べ替えます。最大ヒープでは、どの親も子以上の大きさです。すると最大値が一番上に来ます。それを末尾と交換して確定させ、ヒープを修復し、これを繰り返します。アプリは棒の上にヒープを木として描くので、各値がふるい落とされる様子を追えます。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。棒の上の木は、同じ値をヒープとして表示します。タイルには比較回数、交換回数、ヒープから取り出した値の数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
- 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
- 木に注目しましょう。まずヒープが完成するまで各親がふるい落とされ、次に根が末尾と交換されてヒープが1つ小さくなります。
ヒープソートのしくみ
リストを木として読みます。位置 i の値の子は、位置 2i + 1 と 2i + 2 にあります。最後の親から始めて各親をふるい落とし、最大ヒープを作ります。値が大きい方の子より小さい間は、2つを交換します。根に最大値が来たら、ヒープの最後の値と交換します。その値は確定し、ヒープは1つ短くなり、新しい根をふるい落として再びヒープにします。ヒープが空になるまで繰り返します。
常に n log n、インプレース
木の段数は約 log₂ n なので、1回のふるい落としは多くても約 2 log₂ n 回の比較で、ヒープの構築は 2n 回未満です。そのためヒープソートは最悪でも約 2n log₂ n 回の比較で済み、バッファも要りません。40個の値なら最大352回です。クイックソートと違って苦手な入力がなく、マージソートと違って追加メモリも要りません。ただ実際には、リストのあちこちに飛ぶため、たいてい両方より遅く、安定でもありません。
よくある質問
ヒープソートはどのように動きますか?
リストを最大ヒープにします。最大ヒープはリストの中に格納された木で、どの親も子以上の大きさです。次に、根にある最大値をヒープの末尾と交換し、新しい根をふるい落としてヒープを修復する操作を繰り返します。
ヒープとは何ですか?
ポインタなしでリストに格納された完全二分木です。位置 i の子は位置 2i + 1 と 2i + 2 です。最大ヒープではどの親も子以上の大きさなので、最大値は常に根、つまり位置 0 にあります。
ヒープの構築はなぜ速いのですか?
ほとんどの値は木の下の方にあり、1〜2段しかふるい落とせません。すべての段の作業を合計すると、構築全体の比較は n log n 回ではなく 2n 回未満です。
ヒープソートは安定ですか?
いいえ。根を末尾と交換すると値が遠くまで移動するので、等しい値の順序が変わることがあります。
入力した数値はどこかに送信されますか?
いいえ。並べ替えはブラウザ内で動き、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ