CodeZine(コードジン)

特集ページ一覧

ヒープソートのアルゴリズム

拡張メソッドでIListをソートする

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2009/05/13 14:00

 ヒープソートは、ソート・アルゴリズムのなかではバブルソートやクイックソートに比べて少しばかりマイナーかも知れません。けれども性能はなかなかに優秀、優先順位付きのキュー(First-In/First-Outバッファ)としても使えます。この記事ではヒープソートのアルゴリズムを解説し、C#の拡張メソッドによる実装を試みます。

目次

ヒープとは

 配列ar[0]...ar[N-1]を考えましょう。配列は各要素が線型に並んだ集合です。ここで配列の各要素をnode(ノード/節)と呼ぶことにします。i番目のnode ar[i]に対してar[2*i+1]ar[2*i+2]の2つのnodeをar[i]の「」、ar[i]を子nodeの「」と呼びましょう(fig-01)。

fig-01
fig-01

 この対応付けによって、配列の各要素はar[0]をroot(ルート/根)としてその子node、さらにその子node……のように漏れ/重複なくたどることができます(fig-02)。

fig-02
fig-02

 つまりこの線型な要素の並びは二分木(BinaryTree)と見立てることができるわけです(fig-03)。

 

fig-03
fig-03

 さて、ここで「木の中にある各節について、親は子より小さくない(親 >= 子)」という条件を与えます。この条件を満たした例を fig-04 に示します。この条件:「親は子より小さくない」を満たした木をheap(ヒープ)と呼びましょう。

fig-04
fig-04

ヒープに要素を追加する

 fig-04で示すヒープに要素を追加する方法を考えます。このヒープの末尾、すなわち配列の末尾に要素「9」を追加しました(fig-05)。

fig-05
fig-05

 追加した要素がその親(ここでは「7」)より大きくなければヒープの条件を満たすので要素の追加はこれで完了です。ところがここで追加した要素「9」は親より大きく、ヒープの条件を満たしません。そこで追加した要素「9」とその親「7」とを交換します(fig-06)。

fig-06
fig-06

 処理はこれで終わりではありません。親子の交換によって親の値が変化したのですから、さらにその上の親との間でヒープ条件を満たすかを確認し、大小関係が壊れていたら(親 < 子なら)交換しなければなりません。この処理を親子の大小関係が整うまで繰り返します(fig-07)。

fig-07
fig-07

  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2009/05/17 21:16 Genericパラメータの欠落を修正

あなたにオススメ

著者プロフィール

  • επιστημη(エピステーメー)

    C++に首まで浸かったプログラマ。 Microsoft MVP, Visual C++ (2004.01~2018.06) "だった"り わんくま同盟でたまにセッションスピーカやったり 中国茶淹れてにわか茶人を気取ってたり、 あと Facebook とか。 著書: - STL標準...

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5