先頭へ戻る

ヒープソート | Programming Place Plus 用語集

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

ソートのアルゴリズムの一種で、二分ヒープの特徴を活かしてソートを行うものです。

二分ヒープ(単にヒープと呼ぶことが多い)は、木構造の一種で、二分木のかたちをしており(つまり、あるの子の数は2つ以内)、配列を使って実装できます。親が子よりも大きいか等しい(あるいは小さいか等しい)というルールを常に満たすように構成されるため、いつも根(一番上位の節)に最大値(あるいは最小値)のデータがあります。

ヒープソートの手順としては、まずソートしたいデータ列をヒープに1つずつ登録していきます。追加のたびに、ヒープとしての要件を満たすように構築されていきます。

すべてのデータの登録が終わったら、根を取り出してはヒープを再構成することを、ヒープが空になるまで繰り返します。根にはいつも最大値(あるいは最小値)のデータがあるので、この手順を繰り返すと、ソートされたデータ列が得られます。

ヒープソートの計算量は O(n log n) で、パフォーマンスが元のデータの並び方に影響されない特徴があります。また、ヒープを実装する配列の中ですべての作業を行え、追加のメモリ領域を必要としないことも特徴的です。安定なソートではありません(同等なデータが複数あったとき、ソート後にそれらの位置関係が崩れる可能性がある)。処理を並列化できないことが欠点とされる場合があります。

C言語によるヒープソートの解説が、アルゴリズムとデータ構造編【整列】第8章にあります。


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー