RSS
ソートのアルゴリズムの一種で、二分ヒープの特徴を活かしてソートを行うものです。
二分ヒープ（単にヒープと呼ぶことが多い）は、木構造の一種で、二分木のかたちをしており（つまり、ある節の子の数は２つ以内）、配列を使って実装できます。親が子よりも大きいか等しい（あるいは小さいか等しい）というルールを常に満たすように構成されるため、いつも根（一番上位の節）に最大値（あるいは最小値）のデータがあります。
ヒープソートの手順としては、まずソートしたいデータ列をヒープに１つずつ登録していきます。追加のたびに、ヒープとしての要件を満たすように構築されていきます。
すべてのデータの登録が終わったら、根を取り出してはヒープを再構成することを、ヒープが空になるまで繰り返します。根にはいつも最大値（あるいは最小値）のデータがあるので、この手順を繰り返すと、ソートされたデータ列が得られます。
ヒープソートの計算量は O(n log n) で、パフォーマンスが元のデータの並び方に影響されない特徴があります。また、ヒープを実装する配列の中ですべての作業を行え、追加のメモリ領域を必要としないことも特徴的です。安定なソートではありません（同等なデータが複数あったとき、ソート後にそれらの位置関係が崩れる可能性がある）。処理を並列化できないことが欠点とされる場合があります。
Ｃ言語によるヒープソートの解説が、アルゴリズムとデータ構造編【整列】第８章にあります。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |