解説 5月24日A

今回の学習項目です。


ヒープを用いたソート

教科書の3,2節(29ページ〜33ページ)を読んでください (注意: ヒープソートについて特に注意して読んでください)。

いろいろな数を要素とする配列があるとします。これをソートすることを考えます。 Rubyの復習では、挿入ソート、選択ソート、クイックソート、マージソートの方法を学んできました。ここではヒープを用いたソートの方法を学びます。

ヒープを用いたソートは次のステップにより行います。ここで、ソートの結果を納める配列(初期値は空とする)を予め用意しておき、変数answerに代入しておくものとします。

  1. 与えられた配列からヒープを作ります。元の配列の要素数をnとすると、n個の頂点を持つヒープを作ります。ここではヒープも配列で表すこととすると、同じ個数の要素を持つ配列ができます。
    注意: ヒープの条件2がありますので、配列の要素の順番と頂点の番号とは一致しません。 これをどのようにして行うかがポイントの一つです。
  2. 根(配列でヒープを表現している場合は指標が1の要素)を取り出してanswerに付け加えます。 その要素がヒープの唯一の要素だった場合は、answerを逆順に並び替えます。これが元の配列の要素をソートした結果となり、ヒープソートが完成です。
  3. (上の操作で根の要素を取り出してもまだヒープに要素がある場合) ヒープの頂点のうちの最後の要素(配列でヒープを表現している場合は、配列の最後の要素)を削除し、その頂点に付随する数値を根の頂点に格納します(配列でヒープを表現している場合は、指標が1の要素の値とします)。
  4. 上記の操作でヒープの条件2が満たされなくなっているはずなので、ヒープの条件2を満たすように作り変えます。この操作もヒープソートを行う時のポイントです。そして2に戻る。
これらの操作によりソートが実際にできることを示す前に、一つ一つの操作について説明します。 ここでは、ヒープを配列で表すものとします。また、1の操作を「ヒープの作成」、 4の操作を「ヒープの修復」と呼ぶことにします。

「ヒープの作成」ではヒープに頂点が一つずつ付け加えられ、結果として新たなヒープができます。 「ヒープの修復」では、頂点の個数は変わりませんが、ヒープの条件2を満たしていない2進木から、 いくつかの頂点に格納した値を(配列で表現している場合は配列の要素を)交換することにより条件2を満たす2進木に作り変えることになります。

「ヒープの作成」操作

「ヒープの作成」は次の操作によってできます。

  1. 元の配列から要素を取り出し、「ヒープの条件1」を満たすように作成中のヒープに頂点を付け加え、 その頂点に取り出した要素(数)を格納します。ここでは配列によってヒープを表すとすれば、 「ヒープの条件1を満たすように頂点を付け加える」ということは(とっても簡単なことに) 「ヒープを表す配列(の最後)に、取り出した要素を付け加える」こととなります。
  2. ただ、単に付け加えただけでは、「ヒープの条件2」を満たしているとは限りません。 ここで「ヒープの条件2」とはどの頂点uと頂点vに対しても、頂点uが頂点vの親であれば,f(u) ≥ f(v)でした(ここで、f(u)は頂点uに格納された値のことです)。そこで、この条件を満たすよう、 必要ならば子の頂点に格納された値と親の頂点に格納された値を交換する、という操作を行います。 そしてこの操作をくり返します。
教科書p.30の図3.3を見て下さい(下にその一部を示します)。 図3.3は、配列[8,5,7,3,10,9,6,1,20]の要素から上記の操作によってヒープを作る過程を表しています。8が配列の先頭の要素なので、まずそれをヒープの根に格納します。次に5を根の左の子頂点に格納します。8 ≥ 5が成り立ちます。同様に7を根の右の子頂点に格納します。8 ≥ 7が成り立っているので、図3.3(a)はヒープの条件を満たしています。

Make Heap Tee
図3.3の一部。赤は付け加えられた要素、青はその親頂点、緑は交換された要素を表す

4番目の要素である3を付け加えたところ(図3.3(b))までは問題ないと思います。次の要素の10を付け加えたところ(図3.3(c))、 その親の要素が5ですから「ヒープ条件2」が満たされていません。 そこで付け加えた要素である10とその親要素の5を交換します(図3.3(d))。 ここで再度「ヒープ条件2」が満たされているかどうか調べます。 この時、付け加えられた要素である10とその親の要素(今は8が親になっていることに注意)とを比べます。 つまり、「ヒープ条件2が満たされているかどうか」は、付け加えられた要素とその親を比べればよい、 ということがわかります。そして「ヒープ条件2が満たされていない」場合は、 付け加えられた要素と親の要素を交換し、再度「ヒープ条件2が満たされているかどうか」を調べれば良いのです。

課題1-1

配列によってヒープを表すことにします。図3.3の(a)から(h)までを配列で表現してください。 そして、最後の(h)がヒープの条件をすべて満たしていることを確かめなさい。
注意: 配列によってヒープを表す場合、0番目の要素は使いませんので、nilを与えておいてください。

課題1-2

配列によってヒープを表すことにします。図3.3(h)のヒープに20を付け加えたとします。 「ヒープの作成」によってその結果できたヒープがどのようなものかを報告しなさい。
注意: 配列によってヒープを表す場合、0番目の要素は使いませんので、nilを与えておいてください。

課題1-3

いま、あるヒープの頂点の個数をnとする。このヒープの高さはおおよそどのくらいか、 nを使って表してみよ。また、このヒープに一個要素を付け加えた時に、 (ヒープ条件2が破られたために)要素を交換する操作は最大何回くらい起こると考えられるか、 答えよ。

課題1-4

n個の要素を持つ配列から上に述べた手順で「ヒープを作成」するとすれば、 どのくらいの計算量が必要と考えられるか?「要素を付け加える」 「親頂点と子頂点の要素を比較する」「親頂点と子頂点の要素を交換する」などの操作は みな計算量1として考えよ。また計算の根拠も示すこと。

「ヒープの修復」操作

課題1-2によって配列[8,5,7,3,10,9,6,1,20]からヒープができたとします。 その時、根には20が格納されており、ヒープの最後の要素には3が格納されているはずです。 Heap Restoration (1) Heap Restoration (2) ここで、ヒープソートの手順2により、根の要素である20は配列answerに入れられ、 最後の要素である3を根に格納します。その状況が左図によって示されています。 この状況ではヒープの条件2が満たされていません。つまり根(この場合3)はその子に格納された要素よりも小さくなっています。 そこで「根の左の子と右の子に格納された値を比較し、大きいほうの要素と根を交換」します。この例では左の子の10と交換します。その結果が右図です。
見てわかるように、これでもまだヒープの条件2が満たされていません。今度も交換された要素(やはり3です)はその子の要素よりも小さくなっています。 そこでまたもや左の子と右の子の「値が大きい」方と交換します。 このように、ヒープ条件2が満たされるまで、要素の交換を続けます。 その結果、ヒープが再生することになります。

課題1-5

配列によってヒープを表すことにします。左の図を配列で表しなさい。そして、ヒープの修復後のヒープを配列で表しなさい。

課題1-6

課題1-5の結果得られたヒープに対して、またもやヒープの最後の要素を取り除き、その値を根に格納することにします。配列を用いてその状態の2進木を表現しなさい。 そしてその木に対してヒープの修復を行った後のヒープを配列で表しなさい。

ヒープソート

繰り返しになりますが、ヒープの作成と、「ヒープの根の要素の除去とヒープの修復」の繰り返し、という二つからヒープソートは構成されます。

  1. ヒープの作成: 与えられた配列からヒープを作ります
  2. 根(配列でヒープを表現している場合は指標が1の要素)を取り出してanswerに付け加えます。 その要素がヒープの唯一の要素だった場合は、answerを逆順に並び替えます。これが元の配列の要素をソートした結果となり、ヒープソートが完成です。
    (上の操作で根の要素を取り出してもまだヒープに要素がある場合) ヒープの頂点のうちの最後の要素(配列でヒープを表現している場合は、配列の最後の要素)を削除し、その頂点に付随する数値を根の頂点に格納します(配列でヒープを表現している場合は、指標が1の要素の値とします)。
  3. ヒープの修復: ヒープの条件2を満たすように作り変えます。そして2に戻る。
ヒープができたとすれば、ヒープの性質(つまり条件2)から、 根に格納されている要素は、その他の頂点に格納されている頂点よりも大きいはずです。 操作1では与えられた配列からヒープを作ります。 操作2と3では、根の要素を取り除いてanswerという配列にいれヒープを修復する、 ということを繰り返します。この繰り返しでは、 つねにヒープの頂点に格納された最大の要素がanswerに移される ということが行われます。したがって、answerには大きな要素から順に入ります。 最後にanswerの値を逆順に並び替えてソートが完成する、というアルゴリズムです。 (注: answerに要素を入れるときに、answerの先頭になるよう挿入するならば、 最後の「逆順に並び替える」ことは不要です)

課題1-7

配列 [15, 8, 7, 5, 6, 9, 16] の要素をヒープソートによりソートしなさい。 ここで、ヒープの作成によって得られたヒープおよびヒープの修復ごとにえられた ヒープを表示すること。また、ヒープは配列によって表現するものとする (配列の指標0の要素にはnilをいれておくこと)

課題1-8

教科書pp.32-33(図3.4)には、与えられた配列からヒープを作成するのもヒープの修復も、 元の配列を用いて行う方法が述べられている。この方式によって課題1-7を行ってみよ。


「アルゴリズムとデータ構造」のホームに戻る