授業の要点が分かる学生のための学習辞典サイト

ヒートソープ【ひーとそーぷ】

ヒープソートとは、2分木を利用したソートアルゴリズムの一種で、整列対象となる配列においてヒープ構造を構築しながら、データの整列を繰り返す。アップヒープ操作によるヒープソートと、ダウンヒープ操作によるヒープソートが存在する。 ヒープソートの計算量は必ずO(n log n)となることが保証されている。

関連した単語

ヒープソートの作業領域とメモリアクセスの特徴

ヒープソートでは、ソートに必要な作業領域が固定サイズで、データ量の大小に関わらず変化しない。スタックのように固定サイズの直線的なデータ構造ではなく、複雑なメモリアクセス方法となる。そのため連続的にメモリへアクセスが出来ず、空間的局所性が失われ、低速なアクセスとなる。また並列処理できないことも、ヒープソートが低速となる要因となっている。 同じキー値を持つデータの順序が、ソート前と比較して一定でないため、安定でないと言われる。コピーなどの処理を伴わないため作業領域は不要である。 アップヒープ操作では、木の根の部分からヒープ構造を構築し、ダウンヒープ操作では木の頂点の部分からヒープ構造を構築していく。

ヒープソートの位置づけ(クイックソートやマージソートとの比較)

ヒープソートはヒープの根にある要素を、データの最終要素に移動することで整列が行われ、構築したヒープを元の配列へ反映させながら処理するというアルゴリズムではない。そのため、クイックソートに見られるような再帰処理、マージソートで見られるような作業領域が不要となっている。 ヒープソートは計算量が低くO(n log n)で済むことから計算量が低いソート方法となっている。一方で、選択ソートとバブルソートでは計算量がO(n^2)ともなり、実用に向かない。クイックソートでも最悪の場合計算量がO(n^2)となることがある。一般にヒープソートよりクイックソートの方が高速であるが、クイックソートでは速度が不安定になることがある点で、ヒープソートの優れている点と言える。

2分木を利用したヒープソートのアルゴリズム

2分木は2分探索木とも呼ばれ、木構造の一種である。2分木とは、親が全て1個か2個の子要素を持っているデータ構造である。データを追加する際は、子を持たない子の下に追加して親にするか、1個の子を持っている親の下に追加する。数値を2分木の配列に並べたデータにおいて、親が全て子より大きな値となっていれば、これをヒープ構造と呼べる。 ヒープ構造に親より数の大きい子を追加すると、ヒープ構造ではなくなる。ヒープソートを行う際は、逆転した親子関係の部分で数値の入れ替えを行う。これを繰り返し、入れ替えた箇所の親が子より大きな数となっていればソートを終了する。

問題

ヒープソートの手順について説明しなさい。ただし、整列対象の配列はn個のデータを持ち、インデックスは1からnとする。

答えを見る

カテゴリ内ランキング

cacicoテキスト買取
cacicoテキスト