ヒープソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

このページにはプロモーションが含まれています

このページではソートアルゴリズムの１つである「ヒープソート」について解説します。

ソートがどのようなものであるかは下記ページの冒頭で解説していますので、まずソートについて知りたい方は先にこちらを読んでみてください。

クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

Contents

ヒープソートとは
二分ヒープの作成
- 二分ヒープを作成する考え方
- 二分ヒープを作成する関数
根ノード取り出し後の二分ヒープの再構成
ヒープソートのプログラム
まとめ

ヒープソートとは

ヒープソートは「二分ヒープ木」の特徴を利用してソートを行うソートアルゴリズムになります。

ヒープソートの特徴

ヒープソートには下記のような特徴があります。

ソート速度が速い
使用メモリが少ない（配列一つ分でソートできる）
アルゴリズムはちょっと難解

ヒープソートは「選択ソート」や「挿入ソート」などに比べるとちょっとアルゴリズムは難解です。

ただし、その反面「ソートが高速に行える」というメリットがあります。またマージソートなどに比べて使用メモリが少ないというメリットもあります。

特に “データ数が多い” 場合にメリットが大きいソートアルゴリズムとなります。

ヒープソートの鍵となる「二分ヒープ」

このヒープソートを理解する上では、まず「二分ヒープ」について理解する必要があります。

なので、ここで簡単に二分ヒープについて解説しておきます。

二分ヒープは全てのノードにおいて、下記が成立する二分木となります。

親ノードのデータ ≧ 子ノードのデータ

例えば下の図は二分ヒープの一例になります。

この大小関係は逆でも良いです。

要は、二分ヒープの全てのノードにおいて、親ノードと子ノードのデータの大小関係が一貫していれば良いです。

例えばデータを “降順に” ソートするような場合は、全てのノードにおいて下記が成立するように二分ヒープを作成します。

親ノードのデータ ≦ 子ノードのデータ

ただし、今回はデータを “昇順に” ソートする例を用いて解説をしていきますので、全てのノードで前述の下記の条件が成立するように二分ヒープを作成する前提で解説していきたいと思います。

親ノードのデータ ≧ 子ノードのデータ

ちなみに、このように子ノードと親ノードの大小関係が全て一致している木構造のことを「ヒープ」と呼びます。

ヒープソートの「ヒープ」はここから来ています（メモリ領域のヒープ領域からきているわけではないです）。

で、この関係を全てのノードが満たす場合、二分ヒープ内に存在するデータの中で、必ず根ノードのデータが一番大きいデータとなります

MEMO

根ノードとは一番上側の親ノードを持たないノードのことを言います

逆に最下層の子ノードを持たないノードのことを、葉ノードと言います

ヒープソートを行う上で一番重要なポイントは、この「二分ヒープ内の最大のデータは必ず根ノードに存在する」点です。

ヒープソートの考え方

では、次はヒープソートの考え方を説明していきます。

ヒープソートは、ソートしたいデータから「二分ヒープ」を作成した後、その「二分ヒープ」からの根ノードの取り出しと「二分ヒープ」の再構成を繰り返すことでソートを行うアルゴリズムになります。

で、おそらくこれだけだと意味不明だと思いますので、図を使って分かりやすく説明していきます。今回は昇順にソートする例を用いて説明していきます。

ヒープソートを行う際には、まずソートしたいデータから「二分ヒープ」を作成します。昇順にソートするため、全ノードが “親ノードのデータ ≧ 子ノードのデータ” の条件が成立するように作成します。

前述の通り、このように作成した二分ヒープでは、必ず「根ノード」が二分ヒープ内の最大のデータになります。

つまり、根ノードのデータが、データ全体の中の「最大のデータ」であることがこの時点で確定します。

なので、根ノードのデータは既にソート済みとして、二分ヒープから取り出してソート済みの集合に移動します。

ただし、根ノードを取り出すことによって木が二分ヒープで無くなってしまいます。

なので、根ノード取り出し後の木を二分ヒープに再構成します。

で、二分ヒープが再構成できれば、また二分ヒープ内の最大のデータが「根ノード」に移動することになります。

先ほど二分ヒープから元々のデータ全体の１番大きいデータを取り除きましたので、この「根ノード」のデータは元々のデータ全体の２番目に大きいデータと言えますね！

なので、この根ノードのデータも既にソート済みとして、二分ヒープから取り出してソート済みの集合の先頭に移動します。

そして、また根ノードを二分ヒープから取り除いてから、また二分ヒープを再構成します。

すると、今度は３番目に大きいデータが根ノードに移動しますので、このデータも３番目に大きいデータとしてソート済みの集合の先頭に移動します。

この後も同様ですね！

つまり、最初にデータ全体から二分ヒープを作成すれば、後は根ノードの取り出しと二分ヒープの再構成を行うことで、どんどんデータをソートすることができます。

二分ヒープからデータが無くなったらソートは完了です。

要は、ヒープソートは、与えられたデータの集合に対して下記を行うことでソートを行うアルゴリズムになります。

データ全体から二分ヒープを作成する
根ノードを取り出してソート済みの集合の先頭に移動する
- 取り出し後の木のデータ数が 0 になったらソート完了
取り出し後の木を二分ヒープに再構成する
2. に戻る

おそらく、ソートされる仕組みはすんなり理解できたのではないかと思います。

ただし、ここまでの解説では、このソートを行うために必要な下記の処理の詳細の説明が抜けています。

二分ヒープの作成方法
根ノード取り出し後の二分ヒープの再構成方法

ではこれらはどのようにして実現すれば良いのか？この点について詳細を解説していきたいと思います。

二分ヒープの作成

では、まずは「二分ヒープ」を作成する方法について解説していきたいと思います。

二分ヒープを作成する考え方

今回は二分ヒープを下記の考え方で作成していきたいと思います。

ノードを二分ヒープに追加する
（追加することで二分ヒープでなくなったのであれば）二分ヒープを再構成する

空の二分ヒープに対して、これらを “二分ヒープに追加したいデータ数分だけ” 繰り返すことで、二分ヒープを作成します。

要は、たくさんノードが存在する二分木を “一気に” 二分ヒープの構成に変形するのではなくて、

ノードを１つ追加する度に二分ヒープを満たすように再構成し、その後に次のノードを追加していくという考え方で二分ヒープを作成するということです。

なぜこの考え方を採用したかというと、単純に二分ヒープが簡単に作れるからです。

では、これら２つの処理が具体的にどのようなものであるかについて、実例を用いて解説していきたいと思います。

ノードを二分ヒープに追加する
（追加することで二分ヒープでなくなったのであれば）二分ヒープを再構成する

二分ヒープへのノードの追加

例えば、現状の二分ヒープが下の図のような構成であるとし、ここにデータ 8 をノードとして追加することを考えてみましょう！

まず、ノードを追加する位置はヒープの最下層です。今回はノードを追加するときは左詰めで追加するようにしたいので、下の図の位置にノードを追加します。

ただ、追加後の図を見ていただいても分かる通り、このデータの追加によって、追加ノードとその親ノードとの大小関係が崩れてしまっていますね。

親ノードとの大小関係も考慮せずに、単に最下層にデータを追加しているだけなので、当然この時に親子の大小関係が崩れてしまう可能性があります。この場合、この木は二分ヒープとは言えません…。

なので、続いてノード追加後の木を二分ヒープに再構成していきます。

ノード追加後の二分ヒープの再構成

この「ノード追加後の二分ヒープの再構成」で行うことは「追加ノードの根の方向への移動」です。

「二分ヒープを満たすまで」追加ノードを根の方向に移動していきます。

また、この移動は、追加ノードとその親ノードの「位置を入れ替える」ことで行います。

要は、ノード追加後の二分木が二分ヒープになっていない原因は、追加ノードのデータが大きいにも関わらず最下層に存在していることです。

逆に考えると、追加ノードの親ノードのデータは小さいにも関わらず、追加ノードよりも根の方向に存在してしまっていることが原因とも言えます。

つまり、追加ノードとその親ノードの位置関係が逆になってしまっています。下記の関係になっているということですね。

親ノードのデータ ≦ 子ノードのデータ（追加ノードのデータ）

なので、追加ノードとその親ノードの位置関係を逆にするために、この２つの位置を入れ替えます。

これにより、追加ノードが一段階根の方向に移動することになります。

ただしこの追加ノードの移動により、移動後の追加ノードとその親ノードとで、また位置関係が逆になってしまっています。

なので、先ほど同様に、この２つの位置を入れ替えます。これにより、また追加ノードが根ノードの方向に一段階移動したことになります。

入れ替え後の二分木を確認してみましょう！今度は、移動後の追加ノードとその親ノードの間で下記の関係が成立しています。

親ノードのデータ ≧ 子ノードのデータ（追加ノードのデータ）

つまり、この時点で二分ヒープを満たすための追加ノードの位置が確定したことになります。木全体としても、しっかり二分ヒープを満たしていますね！

こんな感じで、ノードを二分ヒープの最下層に追加することで二分ヒープが満たされなくなった場合、追加ノードと親ノードとの位置の交換により追加ノードを根の方向に移動していくことで、いずれ二分ヒープが満たされる位置に追加ノードが移動することになります。

つまり、ノード追加後の二分ヒープの再構成は下記を行うことで実現することができます。

追加ノードと親ノードの大小関係が満たされているかどうかを確認
- 満たされている場合は、二分ヒープの再構成は完了
追加ノードと親ノードの位置を入れ替える
- 追加ノードの位置が根ノードの位置になったら、二分ヒープの再構成は完了
、1. に戻る

元々二分ヒープである二分木に対してノードを追加した場合、ノードの交換を行う必要がある可能性があるのは「追加ノード〜根ノードまで」の経路上のノードのみです。

なので、ノード追加後の二分木を二分ヒープに再構成するためには、追加ノードから親ノードをたどりながらノードの交換を行えば良いだけなので処理が単純になります。

二分ヒープを作成する関数

ここまで説明してきた「二分ヒープの作成方法」をしっかり理解していただくために、ここでC言語で記述した「二分ヒープを作成する関数」を紹介しておきます。

二分ヒープの作成

/* a[size]を二分ヒープに追加し、二分ヒープを再構成する */
void addHeap(int a[], int size) {

    int add; /* 追加ノードの位置 */
    int parent; /* 追加ノードの親の位置 */

    /* まだ二分ヒープに追加していないデータの先頭を二分ヒープに追加 */
    add = size;
    if (add == 0) {
        /* 追加したノードが根ノードなら二分ヒープへの追加完了 */
        return;
    }

    /* 二分ヒープを満たすまで、追加したノードを根の方向に移動する */
    while (1) {
        /* 親ノードの位置を取得 */
        parent = getParent(add);
        
        if (a[parent] < a[add]) {
            /* 親と子で大小関係が逆ならデータを交換する */
            swap(&a[parent], &a[add]);

            /* 追加ノードは親ノードの位置に移動する */
            add = parent;
            if (add == 0) {
                /* 追加ノードが根ノードまで移動したら二分ヒープへの追加完了 */
                break;
            }
        } else {
            /* 大小関係が満たされているなら二分ヒープへの追加完了 */
            break;
        }
    }
}

/* 二分ヒープを作成する関数 */
void makeHeap(int a[], int num) {

    int size; /* 二分ヒープに追加済みのデータの個数 */

    /* 二分ヒープのデータ個数を0にする */
    size = 0;

    /* sizeがソートするデータの個数になるまで二分ヒープにデータ追加 */
    while (size < num) {

        /* a[size]を二分ヒープに追加 */
        addHeap(a, size);

        /* 二分ヒープのデータ数が増えたのでsizeも1増やす */
        size++;
    }
}

主な関数の概要

makeHeap 関数が二分ヒープを作成する関数です。

makeHeap 関数の引数 a がソートするデータを格納した配列で、引数 num がソートするデータの個数になります。

さらに、makeHeap 関数から呼び出している addHeap がヒープにノードを追加し、追加後の二分木を二分ヒープに再構成する関数になります。

addHeap の引数 a は、後述で説明する「二分ヒープに追加したノードのデータ」と「まだ二分ヒープに追加していないデータ」の２種類のデータを格納する配列になります。

また、引数 size は関数実行時の「二分ヒープのノードの個数」になります。

addHeap 関数が行う処理は「まだ二分ヒープに追加していないデータ」の “先頭データ” を二分ヒープにノードとして追加する処理と、

ノードの追加後、二分ヒープを満たさなくなった場合に、二分ヒープの再構成を行う処理の２つになります。

配列でのデータの扱い

ポイントの１つが「配列 a でのデータの扱い方」です。

この配列では、下記のように２つの種類のデータを区別して扱っています（１つの配列の中で２つの種類のデータを扱っているのでちょっと分かりにくいですが、これにより配列１つ分のメモリでソートを行うことができます）。

配列の前半部分：二分ヒープに追加したノードのデータ
配列の後半部分：まだ二分ヒープに追加していないデータ

配列の前半部分は二分ヒープに追加済みのノードのデータを表しており、この部分の各要素は、先頭側の要素から順に二分ヒープの上側（さらには左側）のノードであるものとして扱います。

また、配列の前半部分と後半部分の区切りの添字は、makeHeap 関数で使用している変数 size で管理します。

この size は「二分ヒープのノード」の個数を管理する変数です。

ですので、配列の各要素はそれぞれ下記を表すことになります。

〜 a[size - 1]：二分ヒープに追加したノードのデータ
a[size] 〜：まだ二分ヒープに追加していないデータ

最初の段階だと、まだ二分ヒープは空なので size = 0 であり、配列の全ての要素が「まだ二分ヒープに追加していないデータ」となります。

で、その状態で addHeap 関数を実行すると、二分ヒープに「まだ二分ヒープに追加していないデータ」の先頭がノードとして追加されます。

つまり、addHeap を実行することで「二分ヒープに追加したノードのデータ」の個数が１増えます。なので、addHeap 実行後は size を 1 増やすようにしています。

で、この addHeap を size を増加させながら num 回繰り返すことで、num 個のデータ全てを二分ヒープに追加することができます。

この時、配列の先頭、つまり a[0] が根ノードに対応しているので、a[0] が配列 a における最大のデータとなります。

また、addHeap では、ノードの追加だけでなく、二分ヒープを再構成するようにもしているところもポイントです。

配列の前半部分の要素は、前述の通り、先頭側の要素から順に二分ヒープの上側（さらには左側）のノードであるものとして扱っています。

例えば配列が下記の場合は（size = 5 としています）、

二分ヒープとして下の図のようなものを構成していると捉えることができます。

で、この状態で addHeap を実行すると、a[size] がノードとして二分ヒープに追加され、さらに二分ヒープとして下の図のようなものが構成されます。

つまり、addHeap 実行後の配列は下記のようになります（ノードを追加したので size = 6 になります）。

二分ヒープを再構成するために追加ノードの移動が行われるため、下線を引いた部分のように addHeap 実行前後で配列の並びが変化することがあります。

`addHeap` 関数の詳細

では、addHeap 関数で具体的にどのような処理を行なっているかというと、これはノード追加後の二分ヒープの再構成で説明した内容そのままです。

要は、追加ノードを a[size] として、下記の処理を行なっているだけです（a[size] はまだ二分ヒープに追加していないデータの先頭）。

追加ノードと親ノードの大小関係が満たされているかどうかを確認
- 満たされている場合は、二分ヒープの再構成は完了
追加ノードと親ノードの位置を入れ替える
- 追加ノードの位置が根ノードの位置になったら、二分ヒープの再構成は完了
、1. に戻る

ポイントになるとすると、親ノードの位置の計算方法ですかね！

配列の前半部分の要素は、前述の通り、配列の先頭側の要素から順に二分ヒープの上側（さらには左側）のノードであるものとして扱っています。

この時、子ノードに対応する配列の添字を child とすると、その親ノードに対応する配列の添字 parent は下記の式で計算することができます。

親ノードの位置の計算

parent = (child - 1) / 2;

ですので、上記を計算する関数として getParent を用意し、子ノードに対する親ノードのデータが辿れるようにしています。

そして、必要に応じて子ノードと親ノードのデータを swap 関数で交換するようにしています。

これらの関数は最後のヒープソートのプログラムに載せていますので、詳細はこちらで確認してください。

根ノード取り出し後の二分ヒープの再構成

続いて、根ノードを取り出した後の二分木を二分ヒープを再構成するための方法について解説していきます。

根ノード取り出し後に二分ヒープを再構成する考え方

根ノードを取り出すと、下の図のようにもはや二分木とは言い難いデータ構造になってしまいます。

なので、まずは二分木の形を取り戻すために、根ノードの位置に一時的に他のノードを移動させます。

具体的には、二分ヒープの末端のノード（上・左方向から見て一番後ろにあるノード）を根ノードに移動させます（この移動したノードを末端ノードと呼ばせていただきます）。

ただし、一時的に根ノードを移動させただけなので、当然、末端ノードとその子ノードとの間で下記が成立しなくなってしまいます。

親ノードのデータ（末端ノードのデータ） ≧ 子ノードのデータ

つまり、形は二分木にはなったものの、二分ヒープにはまだなっていないということですね。

問題点は、末端ノードのデータが小さいにも関わらず、末端ノードが根ノードに存在してしまっていることです。

なので、ノード追加後の二分ヒープの再構成の時と同様に、末端ノードを移動させていく必要があります。

ただし、ノード追加後の二分ヒープの再構成の時とは異なり、移動させていく方向は「葉の方向」です。

移動の方法も同様で、「子ノードとの位置の入れ替え」です。

ただし、今度は位置の入れ替え先の候補が２つあります。

「左の子ノード」と「右の子ノード」ですね。この場合は、左の子ノードと右の子ノードのうち、”データが大きい方のノード” と位置を入れ替えます。

もしデータが小さい方の子ノードと位置を入れ替えると、もう一方の子ノードよりもデータが小さいノードが親ノードになってしまうので、親子の大小関係が満たされないことになります。

子ノードが１つの場合は候補は１つなので、位置の入れ替えはその子ノードと行います。

上記の「末端ノードとその子ノードとの位置の入れ替え」を行うと、末端ノードが葉の方向に一段階移動することになります。

で、この移動により、移動後の末端ノードとその子ノードとの位置関係が逆になってしまう可能性があります。

この場合は先ほどと同様に末端ノードと子ノードの位置の入れ替えを行っていきます。

こんな感じで、二分ヒープから根ノードの取り出しによって二分ヒープが満たされなくなった場合、末端ノードと子ノードとの位置を交換して末端ノードを葉の方向に移動していくことで、いずれ木全体の二分ヒープが満たされる位置に末端ノードが移動することになります。

つまり、根ノード取り出し後の二分ヒープの再構成は下記を行うことで実現することができます。

根ノードの位置に二分ヒープの末端のノードを移動（ここでは、移動してきたノードを末端ノードと呼ぶ）
末端ノードと子ノードの大小関係が満たされているかどうかを確認
- 満たされている場合は、二分ヒープの再構成は完了
末端ノードと、大きなデータを持つ方の子ノードの位置を入れ替える
- 末端ノードの位置が葉ノードの位置になったら、二分ヒープの再構成は完了
、2. に戻る

ちょっと違った観点で考えると、ヒープソートにおいては、１つのデータを “ソート済み” にするためには上記の処理が必要であるということができます。

つまり、１つのデータを “ソート済み” にするためには、最悪「木の深さ -1」回の交換が必要です。木の深さはデータ数を N とすれば、おおよそ log2 N となりますので、交換回数のオーダーは 0(log 2 N) となります。これを N 個のデータ分繰り返すので、全データをソートする時の交換回数のオーダーは O(N log2 N) となります。

一方で、バブルソートでは１つのデータをソート済みにするには、データ数を N とすれば最悪「N – 1」回の交換が必要です。つまり交換回数オーダーは O(N) となります。これを N 個のデータ分繰り返すので、全データをソートする時の交換回数のオーダーは O(N * N) となります。

この辺りの処理の違いからも、ヒープソートがバブルソートなどの基本的なソートよりも高速であることが直感的に理解できると思います。

根ノード取り出し後に二分ヒープを再構成する関数

ここまでの解説内容を踏まえて作成した「根ノード取り出し後に二分ヒープを再構成する」関数は下記のようになります。

ノード取り出し後に二分ヒープを再構成する

/* 根ノードを二分ヒープから取り出し、二分ヒープを再構成する */
void removeHeap(int a[], int size) {
    int left; /* 左の子ノードの位置 */
    int right; /* 右の子ノードの位置 */ 
    int large; /* データが大きい方の子ノードの位置 */
    int parent; /* 親ノードの位置 */

    /* 根ノードをヒープ外に追い出す */
    /* 一時的に木の末端のノードを根ノードに設定する */
    swap(&a[0], &a[size - 1]);
    
    /* 二分ヒープのサイズを1減らす
        これにより元々の根ノードが「ソート済みのデータ」の先頭に移動することになる */
    size--;

    /* 根ノードから子ノードとの大小関係を確認していく */
    parent = 0;

    /* 二分ヒープを満たすまで、根ノードを葉の方向に移動する */
    while (1) {
        /* 子ノードの位置を取得 */
        left = getLeft(parent);
        right = getRight(parent);

        /* 子ノードの大きい値を持つ方の位置を取得 */
        if (left < size && right < size) {
            /* 左右両方の子ノードが存在する場合は比較して確認 */
            if (a[left] < a[right]) {
                large = right;
            } else {
                large = left;
            }
        } else if (left < size) {
            /* 左の子ノードしか存在しない場合は左の子ノードを大きい値を持つとみなす */
            large = left;
        } else {
            /* 両ノードがヒープ内に存在しない場合は終了 */
            /* (右の子ノードしか存在しない場合はあり得ない) */
            break;
        }

        if (a[large] <= a[parent]) {
            /* すでに親子の大小関係が満たされているので交換不要 */
            break;
        }

        /* 親と子で大小関係が逆ならデータを交換する */
        swap(&a[large], &a[parent]);

        /* 根ノードはデータを交換した子ノードの位置に移動する */
        parent = large;
    }
}

主な関数の概要

removeHeap 関数が二分ヒープの根ノードを取り出し、さらに取り出し後の二分木を二分ヒープに再構成する関数になります。

引数 a は、後述で説明する「二分ヒープに残っているノードのデータ」と「ソート済みのデータ」の２種類のデータを格納した配列になります。

また、引数 size は関数実行時の「二分ヒープに残っているノードの個数」になります。

removeHeap 関数が上記のような処理を行うため、引数 size を 1 ずつ減らしながら、ソートしたいデータの個数分繰り返し実行すれば、「二分ヒープに残っているノードのデータ」が「全てソート済みのデータ」に移動し、データ全体がソートできることになります。

配列でのデータの扱い

二分ヒープを作成する関数同様に、ポイントになるのが「配列 a でのデータの扱い方」です。

removeHeap 関数では、配列 a を下記のように２つの種類のデータとして区別して扱っています。

配列の前半部分：二分ヒープに残っているノードのデータ
配列の後半部分：ソート済みのデータ

配列の前半部分の各要素と二分ヒープの各ノードとの対応は二分ヒープを作成する関数と同様です。

また、配列の前半部分と後半部分の区切りの添字は、removeHeap 関数で使用している変数 size で管理します。

この size は「二分ヒープに残っているノード」の個数を管理する変数です。

ですので、配列の各要素はそれぞれ下記を表すことになります。

〜 a[size - 1]：二分ヒープに残っているノードのデータ
a[size] 〜：ソート済みのデータ

`removeHeap` 関数の詳細

removeHeap 関数では、大きく分けると下記の３つの処理を行なっています。

根ノードを取り出す
取り出したノードのデータをソート済み集合へ移動する
根ノード取り出し後の二分木を二分ヒープに再構成する

この 1. と 2. を行なっているのが下記部分になります。

根ノードの取り出し

    /* 根ノードをヒープ外に追い出す */
    /* 一時的に木の末端のノードを根ノードに設定する */
    swap(&a[0], &a[size - 1]);
    
    /* 二分ヒープのサイズを1減らす
        これにより元々の根ノードが「ソート済みのデータ」の先頭に移動することになる */
    size--;

二分ヒープのノードの個数が size なので、二分ヒープの末端のノードのデータは a[size - 1] となります。

なので、この a[size - 1] と根ノード a[0] のデータを swap 関数で交換します。

これにより、根ノードと末端のノードのデータが入れ替わることになり、木は下の図のように変化します。

さらに、二分ヒープのノード個数 size を -1 してやれば、元々根ノードだったデータは二分ヒープ外に移動します。

配列のデータの取り扱い方を考慮すれば、元々の根ノードのデータは「ソート済みのデータ」の先頭に移動することになります。

以上の処理により、下記の 1. と 2. の処理を実現しています。

根ノードを取り出す
取り出したノードのデータをソート済み集合へ移動する
根ノード取り出し後の二分木を二分ヒープに再構成する

これ以降は、根ノード取り出し後に二分ヒープを再構成する考え方で説明した内容に基づいて 3. の処理を行なっています。

具体的には swap 後の a[0] を末端ノードとして下記を行なっているだけです。

末端ノードと子ノードの大小関係が満たされているかどうかを確認
- 満たされている場合は、二分ヒープの再構成は完了
末端ノードと、大きなデータを持つ方の子ノードの位置を入れ替える
- 末端ノードの位置が葉ノードの位置になったら、二分ヒープの再構成は完了
、1. に戻る

これらの処理を行うためには、親ノードから子ノードの位置を計算する必要があります。

親ノードに対応する配列の添字を parent とすると、左の子ノードに対応する配列の添字 left は下記の式で計算することができます。

左の子ノードの位置の計算

child = parent * 2 + 1;

また、右の子ノードに対応する配列の添字 right は下記の式で計算することができます。

右の子ノードの位置の計算

child = parent * 2 + 2;

ですので、上記を計算する関数として getLeft と getRight を用意し、親ノードから子ノードを辿れるようにしています。

そして、必要に応じて子ノードと親ノードのデータを swap 関数で交換するようにしています。

これらの関数は次のヒープソートのプログラムに載せていますので、詳細はこちらで確認してください。

ヒープソートのプログラム

最後にヒープソートを行うプログラム全体のソースコードを紹介しておきます。

heapSort 関数がヒープソートを実行する関数で、この heapSort 関数から、事前に紹介した makeHeap 関数と removeHeap 関数を実行しています。

main.c

#include <stdio.h>

/* データの数 */
#define NUM 10

/* データを入れ替える関数 */
void swap(int *a, int *b) {
    int tmp;
    tmp = *b;
    *b = *a;
    *a = tmp;
}

/* 左の子ノードの位置を取得 */
int getLeft(int parent) {
    return parent * 2 + 1;
}

/* 左の子ノードの位置を取得 */
int getRight(int parent) {
    return parent * 2 + 2;
}

/* 親ノードの位置を取得 */
int getParent(int child) {
    return (child - 1) / 2;
}

/* a[size]を二分ヒープに追加し、二分ヒープを再構成する */
void addHeap(int a[], int size) {

    int add; /* 追加ノードの位置 */
    int parent; /* 追加ノードの親の位置 */

    /* まだ二分ヒープに追加していないデータの先頭を二分ヒープに追加 */
    add = size;
    if (add == 0) {
        /* 追加したノードが根ノードなら二分ヒープへの追加完了 */
        return;
    }

    /* 二分ヒープを満たすまで、追加したノードを根の方向に移動する */
    while (1) {
        /* 親ノードの位置を取得 */
        parent = getParent(add);
        
        if (a[parent] < a[add]) {
            /* 親と子で大小関係が逆ならデータを交換する */
            swap(&a[parent], &a[add]);

            /* 追加ノードは親ノードの位置に移動する */
            add = parent;
            if (add == 0) {
                /* 追加ノードが根ノードまで移動したら二分ヒープへの追加完了 */
                break;
            }
        } else {
            /* 大小関係が満たされているなら二分ヒープへの追加完了 */
            break;
        }
    }
}

/* 根ノードを二分ヒープから取り出し、二分ヒープを再構成する */
void removeHeap(int a[], int size) {
    int left; /* 左の子ノードの位置 */
    int right; /* 右の子ノードの位置 */ 
    int large; /* データが大きい方の子ノードの位置 */
    int parent; /* 親ノードの位置 */

    /* 根ノードをヒープ外に追い出す */
    /* 一時的に木の末端のノードを根ノードに設定する */
    swap(&a[0], &a[size - 1]);
    
    /* 二分ヒープのサイズを1減らす
        これにより元々の根ノードが「ソート済みのデータ」の先頭に移動することになる */
    size--;

    /* 根ノードから子ノードとの大小関係を確認していく */
    parent = 0;

    /* 二分ヒープを満たすまで、根ノードを葉の方向に移動する */
    while (1) {
        /* 子ノードの位置を取得 */
        left = getLeft(parent);
        right = getRight(parent);

        /* 子ノードの大きい値を持つ方の位置を取得 */
        if (left < size && right < size) {
            /* 左右両方の子ノードが存在する場合は比較して確認 */
            if (a[left] < a[right]) {
                large = right;
            } else {
                large = left;
            }
        } else if (left < size) {
            /* 左の子ノードしか存在しない場合は左の子ノードを大きい値を持つとみなす */
            large = left;
        } else {
            /* 両ノードがヒープ内に存在しない場合は終了 */
            /* (右の子ノードしか存在しない場合はあり得ない) */
            break;
        }

        if (a[large] <= a[parent]) {
            /* すでに親子の大小関係が満たされているので交換不要 */
            break;
        }

        /* 親と子で大小関係が逆ならデータを交換する */
        swap(&a[large], &a[parent]);

        /* 根ノードはデータを交換した子ノードの位置に移動する */
        parent = large;
    }
}

/* 二分ヒープを作成する関数 */
void makeHeap(int a[], int num) {

    int size; /* 二分ヒープに追加済みのデータの個数 */

    /* 二分ヒープのデータ個数を0にする */
    size = 0;

    /* sizeがソートするデータの個数になるまで二分ヒープにデータ追加 */
    while (size < num) {

        /* a[size]を二分ヒープに追加 */
        addHeap(a, size);

        /* 二分ヒープのデータ数が増えたのでsizeも1増やす */
        size++;
    }
}

/* ヒープソートを行う関数 */
void heapSort(int a[], int num) {

    int size; /* 二分ヒープのノード個数 */

    /* サイズnumの二分ヒープを作成 */
    makeHeap(a, num);
    

    /* 二分ヒープの根ノードを１つずつ取り出す */
    for (size = num; size > 0; size--) {
        /* サイズsizeの二分ヒープからデータを１つ取り出す */
        removeHeap(a, size);
    }

}

/* 配列を初期化する関数 */
void initArray(int a[]) {
    a[0] = 5;
    a[1] = 0;
    a[2] = 9;
    a[3] = 7;
    a[4] = 1;
    a[5] = 6;
    a[6] = 3;
    a[7] = 8;
    a[8] = 4;
    a[9] = 2;
}

/* 配列のデータを表示する関数 */
void printArray(int a[], int num){
    int i;
    for (i = 0; i < num; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main(void) {
    int array[NUM];

    /* 配列を初期化 */
    initArray(array);

    /* ソート前の配列の表示 */
    printArray(array, NUM);

    /* ヒープソート */
    heapSort(array, NUM);

    /* ソート後の配列の表示 */
    printArray(array, NUM);

    return 0;

}