ヒープソート【heap sort】

概要

ヒープソート（heap sort）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの一つで、ヒープ構造と呼ばれる二分木の一種を構築して並べ替えを行うもの。

数値の列を先頭から小さい順（昇順）に並べる場合を考える。データ構造の一種である木構造（ツリー）を用意し、未整列のデータを一つずつ取り出して登録していく。親ノードは最大で2つまでの子ノードを持ち（二分木）、親ノードがいずれの子ノードよりも小さく（あるいは大きく）なるように調整しながら追加していく。

このような制約を設けた木構造を「二分ヒープ木」あるいは「ヒープ構造」という。すべてのデータを登録すると、根ノードは全体の中で最も小さいデータとなる。これを取り出して整列済み配列の先頭に入れる。

子ノードのうち、小さいノードを根ノードに移し、その子孫のノードも同様に再構成する。新しい根ノードは残りのデータのうち最も小さいため、これを取り出して整列済み配列に追加する。以下同様に、ヒープ構造からデータがなくなるまで同じ操作を繰り返す。

ヒープ構造は木構造用の制御データを用意しなくても配列内部で表現可能なため、実装上は未整列のデータ列を徐々にヒープ構造に置き換えていき、木が完成したら今度は徐々に整列済みデータ列に置き換えていく。

外部に操作用の記憶領域を用意しなくてよいインプレースソート（内部ソート）で、同じ大きさの要素の順序の維持は保証されない不安定ソートである。平均計算量が O（nlogn）と最も速いソート法の一つで、元のデータ順の影響も受けにくいが、実際にはクイックソートの方が高速になるとされる。

(2024.3.7更新)

この記事の著者： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。