二分木で並べる

前回の「並べる」では、「ヒープソート」を落としていたことに遅まきながら気がついた。何より自身の備忘録でもあるので、追っかけまとめておく。コーディングは余り好きではないが、二分木を知っておくことは必要だろうと、大々昔にプログラムの勉強でやらされたのがこれだったような? プログラム屋になるのではないのに、なんでこんなこと・・、と思った記憶がある。

◇ 二分木で並べる

[ヒープソート]で良いのだが、言葉から動作をイメージしやすいように「二分木で並べる」と題した。選択ソートの一種だろうが、二分木の親が子より小さくない構造を作り続けていき、データをヒープ(二分木)構造化して先頭の値を取り消すことを繰り返す。つまり、未整列リストから先頭に来た最大値の要素を取り出し、順にヒープに追加していく作業を、全要素追加し終わるまで繰り返す。
前回のように鉛筆の例では、間怠っこくなるので付記した「配列手順例」に沿って[2][5][3][8][7]を並べていく。

[2][5][3][8][7]の長さの鉛筆を次のように二分木構造で並べていく
一番下にある子[8][7]と親[5]が「親≧子」になっているか確認する
ここでは子「8」が大きいの「5」と入れ替える
次に一つ上の階層[8][2][3]が「親≧子」になっているか確認する
3つの中で「8」が一番大きいので親[2]と入れ替える
[2]が移動してきたので、左下[2][5][7]のグループが「親≧子」になっているか確認する
[2]が移動してきたので、左下[2][5][7]のグループが「親≧子」になっているか確認する
3つ[2][5][7]の中では[7]が一番大きいので、[2][7]を入れ替える
[ ] [ ] [ ] [ ] [8]「親≧子」になっている二分木構造の完成したので、一番上の根が最大値になった。
この根(ルート)の値[8]を整列済データの最大値とします。
整列済の[8]を除いて未成列データで二本木構造を作る(一番下の[2] を一番上に移動する)
下のグループ[7][5]は既に親≧子」になっている(上図)
上のグループ[2][7]3]を「親≧子」になっているか確認する(上図)
3つ[2][7][3]の中では[7]が一番大きいので、[2][7]を入れ替える(左図)
[2]が移動してきたので、左下[2][5]のグループが「親≧子」になっているか確認する(上図)
[5]が一番大きいので[2][5]を入れ替える
[ ] [ ] [ ] [7] [8]「親≧子」になっている二分木構造の完成したので、一番上の根が最大値になった。
この根(ルート)の値[7]を整列済データの2つめの最大値とします

整列済の[5]を除いて未成列データで二本木構造を作る(一番下の[3] を一番上に移動する)
3つ[2][5][3]の中では[5]が一番大きいので、[2][5]を入れ替える(上左図)
左図は入れ替え後
[ ] [ ] [5] [7] [8]「親≧子」になっている二分木構造の完成したので、一番上の根が最大値になった。
この根(ルート)の値[5]を整列済データの3つ目の最大値とします

整列済の[5]を除いて未成列データで二本木構造を作る(一番下の[3] を一番上に移動する)
[ ] [3] [5] [7] [8][2][3]の中では[3]が一番大きいので
「親≧子」になっている二分木構造の完成したので、一番上の根が最大値になった。
この根(ルート)の値[3]を整列済データの4つ目の最大値とします。
[2] [3] [5] [7] [8]残った「[2]を整列済データの最後に追加してソートは終了

例によってソートダンス

👀
10年前に「ヒープソート」も挙げていたら、このダンス動画はなく、困ったかも。前回のいろいろなソートは、説明よりダンスの方がわかりやすいと感じたが、今回の「ヒープソート」は、少しばかりダンスでは分かり難いかもしれない。

わかりやすい動画がありました。何を苦労して図を書いたのだろう???
 * 下記動画は「アルゴリズム図鑑」さんから共有させていただきました。 

コメント

タイトルとURLをコピーしました