ヒープソート

ヒープ構造の2分木の考え方を応用したソーティング方法。データ構造としては配列で表現する。(本来、配列化されたデータがソーティング対象)

ヒープとは

  • 親>子の構造を持つ2分木
  • 子(兄弟)間の位置関係は自由(特に左右のルールなし。2分探索木とは異なる)

配列構造で2分木を表現

モデルとなる木へのデータ格納順は横型とする。よって、任意の要素(ノード) a[i] について

    • 親:a[(i-1)/2]
    • 子(左):a[i×2+1]
    • 子(右):a[i×2+2 ]

の関係が成立する(剰余は切り捨て)

ヒープ化

    • 末尾を含む部分木からヒープ化
    • 先頭に向かってヒープ部分木を拡大して構成(大きい値の子と交換していけば良い)
    • 最終的に全体がヒープ化される

ソーティングの考え方

ヒープ化されている2分木が対象

  1. ソート対象の配列の末尾とルートを交換(末尾に来たルートはソート済み状態)
  2. もし、1の後、木の状態がヒープでないなら再ヒープ化を行う(交換されたルートを適切な位置へ移動。大きい値の子と交換していけば良い)
  3. 全体がヒープ化されていれば1へ戻る(再びルートを末尾と交換、、、、を繰り返す)
ヒープソート
ヒープソート の問題解答解説