ページ1:

16:29
YE *4 16%
C
カテゴリー
07-18, 16:24
ヒープソート
アルゴリズムの1つ
【 並び替え】 の1つのやり方
イメージは?
上と下の○にはいる数字にルールをを決めて
ヒープを作り、 そのルールを利用して大きい
順、小さい順等並び替える。
やり方書き出してみよーか。
図をノートに書きながらやって
自然にできるようになるまで繰り返す。
親ノード○は子○より大きいっていう
ルール通りのヒープをつくるよ
データを最後尾に追加するよ。
配列なら最後。
ヒープの図なら一番下の段の一番右側
(右側がいっぱいなら1段下げて一番左側)
その追加したデータ○を親の○と比べて
ルール通りになる位置まで上に登ってくよ。
Aa ☑
。 ☑

ページ2:

16:29
YE *4 16%
C
07-18, 16:24
カテゴリー
ての追加したナーを税のU八
ルール通りになる位置まで上に登ってくよ。
ヒープ完成!!
【繰り返し先頭】
そしたら、1番大きいデータを取り出すよ。
それを配列の後ろに整列させるよ。
配列の後ろには元々一番小さいしデータが入
っているから、そのデータがルートに一時的
に来るよ。
その一番小さいデータをヒープのただしい位
置に戻すよ。 1段ずつ比較してくよ。
下にデータが2つあるときは、大きい方と交
換するよ。 小さい方に交換しちゃうと交換し
たあと大小関係が間違っちゃうよ。
大小関係を比較するときは実際
配列の添字をつかってるよ。
左は2n+1右は2n+2 (+の部分0と1使うこと
もあるらしいよ。)
Aa

ページ3:

16:30
YE *46 16%
C
カテゴリー ▼
07-18, 16:24
再構成が終わったらまたルートを取り出す作
業をやるよ。
【繰り返し先頭まで戻る】
メモ
ルートを取り出すのは実際は配列の最後尾に
いれてる。だからヒープのルール壊れる (大
小関係)から整頓し直すよ。
図だと大まかに作成(下から上に上がる作業)
と、整頓(上から下に下がる作業)がある。
配列で考えると最後尾に追加してからただし
い位置にはいる操作と、 先頭データと最後尾
を入れ替えて、 新しく先頭に入ったデータを
ただしい位置に入れる操作。
子ノードとの比較は2n+1や2n+2で子ノード
が入ってる配列の添字を使って子ノードのデ
ータを引っ張ってくる。
ヒープはO記法でいうと
nlog2n表せる。
Aa

ページ4:

16:30
YE *4 16%
C
カテゴリー
07-18, 16:24
ルートを取り出すのは実際は配列の最後尾に
いれてる。だからヒープのルール壊れる (大
小関係)から整頓し直すよ。
図だと大まかに作成(下から上に上がる作業)
と、整頓(上から下に下がる作業) がある。
配列で考えると最後尾に追加してからただし
い位置にはいる操作と、先頭データと最後尾
を入れ替えて、 新しく先頭に入ったデータを
ただしい位置に入れる操作。
子ノードとの比較は2n+1や2n+2で子ノード
が入ってる配列の添字を使って子ノードのデ
ータを引っ張ってくる。
ヒープはO記法でいうと
nlog2n表せる。
↑は別でまとめるから、 今はぴんとこなくて
も気にしなくてok。
Aa
☑

ページ5:

16:41
V *4 10%
G
カテゴリー
07-18, 16:24
https://youtube.com/@bun_ai
文系でもわかる! IT勉強会チャンネル参照
Aa
e