Memo-11.ソートとマージ（７）ヒープソート

ソートとマージについて（７）ヒープソート
- ７．ヒープソート

ソートとマージについて（７）ヒープソート

７．ヒープソート

データを2分木の構造（親の下に子が最大２つあるツリー構造）に配置し、下の階層から　ヒープ条件（親＞＝子、又は、親＜＝子）を満たすように調整すると、最上位の階層の親（ルートノード）に、最大(小)値が移動するという木構造の性質を利用したソート方法です。

7.1　ヒープ構造について

7.2　ソートされていく様子

実際のデータがソートされていく様子です。
サンプルデータは、Data＝（44，13，21，51，8，14，66，9）とします。
（説明が長くなりますが、今までと同じサンプルデータを用います。）
下図は、データを完全2分木の構造に配置してからヒープ化を行っていく様子です。
降順の場合の例ですので、親には部分木の最大値を移動するようにします。

赤枠がヒープ化を行う部分木です。
緑枠はすでにヒープ化されているので作業を行う必要のない部分木です。
文書で説明すると下記のようになります。

１回目　下からヒープ化を行います。
　①　51(親)＞9(子)： このまま次に進みます。
　②　13(親)＜51(子)：51と13 を入れ替えます。
　③　21(親)＜66(子)：66と21を入替えます。
　④　44(親)＜66(子)：44と66を入れ替えます。
　　　→　最大値66が決定します。→　最後尾の9をルートに移動します。
　２回目以降は、ルートから下へヒープ条件を満たしているかを検証します。
２回目　9が移動してきたので、ヒープ条件を満たしているか確認します。
　①　9(親)＜51(子)：51と9を入替えます。
　　　→　9の移動先の左の部分木を確認します。右の部分木は影響をうけません。
　②　9(親)＜13(子)：13と9を入れ替えます。　　　　　　
　　　→　次の最大値51が決定します。→最後尾の21をルートに移動します。
３回目　21が移動してきたので、ヒープ条件を満たしているか確認します。
　①　21(親)＜44(子)：44と21を入れ替えます。
　　　→　21の移動先の右の部分木を確認します。左の部分木は影響をうけません。
　②　21(親)＞14(子)：ヒープ条件を満たしていますので作業は不要です。
　　　→　次の最大値44が決定します。　→最後尾の14をルートに移動します。
４回目　14が移動してきたので、ヒープ条件を満たしているか確認します。
　①　14(親)＜21(子)：21と14を入れ替えます。
　　　左の部分木は影響をうけません。これで終了です。
　　　→　次の最大値21が決定します。→　最後尾の8をルートに移動します。
５回目　8が移動してきたので、ヒープ条件を満たしているか確認します。
　①　8(親)＜14(子)：14と8を入れ替えます。
　　　左の部分木は影響をうけません。これで終了です。
　　　→　次の最大値14が決定します。→　最後尾の9をルートに移動します。
６回目　9が移動してきたので、ヒープ条件を満たしているか確認します。
　①　9(親)＜13(子)：13と9を入れ替えます。
　　　→　次の最大値13が決定します。→　最後尾の8をルートに移動します。
７回目　8が移動してきたので、ヒープ条件を満たしているか確認します。
　①　8(親)＜9(子)：9と8を入れ替えます。
　　　→　次の最大値9が決定します。→　最後尾の8をルートに移動します。
８回目　未ソートのデータ残が一つなので終了、8が最小値です。

いかがでしょうか、比較する回数がかなり少なくて済みます。
ヒープソートが、高速だということが分かります。

7.3　フローチャート

配列　D(n)=D(1),D(2),D(3),・・・D(n-1),D(n) で、親と子の位置関係を数式で表すと
i 番目のデータの左側の子は、i*2、右側の子は　i*2+1 となります。（配列は１起算）
ループ（For文又はWhile文）形式でのフローチャートです。

7.4　VBAコード

7.4.1　メイン処理

Option Compare Database
Option Base 1
Dim data As Variant
Dim wk As Long
-----------------------------------------------------
Public Sub TestHeapSort()	
Dim n As Long	
Dim last As Long	
Dim ix1 As Long	
'sample data	
    data = Array(44, 13, 21, 51, 8, 14, 66, 9)	
    n = UBound(data)	
'最後の親の位置から先頭に向かってヒープ化を行う	
   For ix1 = n \ 2 To 1 Step -1           
        Call Heapify(data, ix1, n)	
   Next ix1	
'Data(1)が最大値となる	
'最後尾の値と入替後、ヒープ条件を満たしているかを確認・回復	
    last = UBound(data)
    Do While last > 1
        wk = data(1)
        data(1) = data(last)
        data(last) = wk
        last = last - 1                    '配列の要素を一つ減ずる
        Call Heapify(data, 1, last)     　 'ルートからヒープ条件を検証
    Loop
End Sub

7.4.2　ヒープ化のサブ

Public Sub Heapify(ByRef arr As Variant, ByVal ix1 As Variant, ByVal last As Variant)	
Dim left As Long	
Dim right As Long	
Dim ix2 As Long	
    ix2 = ix1                             '親の位置	
    Do While True	
        left = ix1 * 2                     '左側の子の位置	
        right = ix1 * 2 + 1                '右側の子の位置	
' 左の子が存在し、かつ親より大きければ,Leftの位置を保存	
        If left <= last Then	
            If arr(ix2) < arr(left) Then	
                ix2 = left	
            End If	
        End If	
' 右の子が存在し、かつ現状の最大値より大きければ,Rightの位置を保存	
        If right <= last Then	
            If arr(ix2) < arr(right) Then	
                ix2 = right	
            End If	
        End If	
'最大値の位置が親でない場合は入れ替え	
        If ix2 <> ix1 Then	
            wk = arr(ix1)	
            arr(ix1) = arr(ix2)	
            arr(ix2) = wk	
            ix1 = ix2	
        Else	
            Exit Do                        '親の位置が部分木の最大値なら終了	
        End If	
    Loop	
End Sub