ヒープソート

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

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

配列構造で2分木を表現
モデルとなる木へのデータ格納順は横型とする。よって、任意の要素(ノード) a[i] について
  • 親:a[(i-1)/2]
  • 子(左):a[i×2+1]
  • 子(右):a[i×2+2 ]
の関係が成立する(剰余は切り捨て)

ヒープ化
  • まずは深さが2のヒープの部分木を構成
  • 深さが3以上にヒープ部分木を拡大して構成(大きい値の子と交換していけば良い)
  • 最終的に全体がヒープ化される

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

ヒープソート





Comments