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

名称

• ヒープソート　【heap sort】

解説

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

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

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

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

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

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