ヒープソートの考え方は、まず、データをヒープ構造にし、完成したらデータの先頭の値を取り出す。そしてまたヒープ構造を作り・・・という繰り返しである。
ここでヒープ構造とは、簡単に言うと、２分木の各節点にデータを保持し、親のデータが2つの子のデータよりも大きくなるように作られたデータ構造である。
つまり、これから分かることは全てのデータの中で２分木の「根」、すなわちデータの先頭に最大値を持つデータが必ず存在する。という事である。
配列Ｎ［］に次のようなデータが格納されているとする。
これを２分木で表現すると、
上図のようになる。
ヒープソートを行うには、まず、この配列（２分木）をヒープ構造にする必要がある。ヒープ構造の特徴は先にも述べた通り、次のようなものである。
では次に、実際にこのデータをヒープ構造にしていく。
ヒープ構造にする際の考え方は以下のようなものである。
文章だけでは理解に苦しむので、図を用いて説明する。
『１』今回の例ではlength = 7 であるので、k = 3 , a = 3 である。
『２』k = 3 より j = 7 と求まる。j = j + 1 には子が存在しないので、N[k] と N[j]の値を比較する。
この時、N[j]の値が最大であるのでこの２つの値を入れ替える。
『３』k = j = 7 とするが、子が存在しないので、a の値を一つ減らし2とする。同様にk = 2 とする。
『２』k = 2 より j = 5 と求まる。j = j + 1 に子が存在するので、N[k] と N[j] と N[j + 1] の値を比較する。
この時、N[j] の値が最大であるのでこの２つの値を入れ替える。
『３』k = j = 5 とするが、子が存在しないので、a の値を一つ減らし1とする。同様にk = 1 とする。
『２』k = 1 より j = 3 と求まる。j = j + 1 に子が存在するので、N[k] と N[j] と N[j + 1] の値を比較する。
この時、N[j + 1] の値が最大であるのでこの２つの値を入れ替える。
『３』k = j + 1 = 4 とするが、子が存在しないので、a の値を一つ減らし0とする。同様にk = 0 とする。
『２』k = 0 より j = 1 と求まる。j = j + 1 に子が存在するので、N[k] と N[j] と N[j + 1] の値を比較する。
この時、N[j] の値が最大であるのでこの２つの値を入れ替える。
k = j = 1 とし、、また、j = 3 とする。ｊ = j + 1 に子が存在するのでN[k] と N[j] と N[j + 1] の値を比較する。
この時、N[j] の値が最大であるのでこの２つの値を入れ替える。
k = j = 3 とし、、また、j = 7 とする。j = j + 1 には子が存在しないので、N[k] と N[j]の値を比較する。
N[k] の値が最大なので、a の値を１つ減らし、k = a とする。
『４』a の値が負となるので、終了である。
以上でヒープ構造が完成する。図を見てもらえば明らかだが、どの親ノードもその子ノードよりも大きな値を持つことが分かる。
ヒープソートを行うには、ヒープ構造の特徴である「根(配列の先頭、N[0])に必ず最大値が来る」という点を利用する｡
この根の部分（配列の先頭）と配列の末尾を入れ替え、配列の末尾を取り除く。残った配列を再びヒープ構造に直す。この１連の操作を繰り返すのがヒープソートである。
では、先程ヒープ構造にした配列Ｎをヒープソートすると、以下のようになる。
以下、同様の操作を続けていくことによってヒープソートが完成する。
なお、ヒープソートのアルゴリズムは以下のように記述できる。
void sort() { // ヒープソート(昇順)
for (int i = (length - 2) / 2; i >= 0; i--) {
downheap(i, length - 1);
}
for (int i = length - 1; i > 0; i--) {
swap(0, i);
downheap(0, i - 1);
}
}
void downheap(int k, int r) {
int j, v;
v = a[k];
while (true) {
j = 2 * k + 1;
if (j > r) break;
if (j != r) {
if (a[j + 1] > a[j]) {
j = j + 1;
}
}
if (v >= a[j]) break;
a[k] = a[j];
k = j;
}
a[k] = v;
}
void swap(int i, int j) { // 要素の交換
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
※プログラム引用
Lecture of Computer Programming I by Hiroshi Ichijiでは実際にアプレットを動かしてみる。
まず数字の書いたボタンをクリックする。
その数字の数だけノードが表示される。
以下は、上に書いた説明に従ってソートすべき２つのノードをドラッグアンドドロップする。