解説 5月17日B

今日の学習項目です。


ヒープ

教科書の3,2節(29ページ〜33ページ)を読んでください。 (注意: ヒープソートについても述べられていますが、ヒープソートについては後日扱います)

ヒープとは定義3.2に述べられた2つの条件を満たす2進木のことです。

定義3.2 (ヒープ)
2進木Tにおいて、それぞれの頂点に値が格納されているとする(ここでは、頂点を vとすると、その頂点vに格納された値が f(v) で参照されるとする。なお、頂点に格納した値をその頂点の「ラベル」とみてもよい)。 以下の2つの条件を満たせば、Tはヒープ(heap)である。 Binary Tee
  1. kを木Tの高さとする。Tでは深さk-1以下の可能な頂点はすべて使われ、 深さkの頂点は左から順に使われている。
  2. どの頂点uと頂点vに対しても、頂点uが頂点vの親であれば,f(u) ≥ f(v)

これでも少しはわかりやすく書きなおしたつもりであるが、それでもわかりにくいところがある。 例えば条件1の「可能な頂点が使われている」とは何であろうか。 また「左から順に使われている」とは何を意味するのだろうか。

それを説明しようとしたのが右図である。 高さ1の2進木を考えよう。高さ1の2進木の場合は 図にあるように、高さ1の2進木を構成する頂点の候補として ①と②、③の3つの頂点がある。これらを「可能な頂点」と呼ぶ。

ここで(1)と(2)はいずれも高さ1の2進木である。 ここで木の頂点として現れていることを「使われている」と呼ぶ。 つまり、(1)では ①と②の頂点が使われ、③の頂点は使われていない。 それに対し、 (2)では①と③の 頂点が使われ、 ②の頂点は使われていない。

また、(1)では深さ1の頂点は「左から順に使われている」 (すなわち、可能な頂点のうち左の頂点から使われている)が、 (2)はそうではない(実際、最も左の頂点が「使われていない」)。

課題1-1

右図は、高さ2の2進木における「可能な頂点」を表している。 頂点には順にv1, v2, ..., v7とラベルがふられている。 Binary Tee

ここで、v1-v2 と頂点のラベルを書くことで2進木を表すものとする。 つまり先の図の番号を用いると、 v1-v2は高さ1の2進木の(1)を、v1-v3は高さ1の2進木の(2)を表すものとする。 さらに、これらの頂点をすべて使った2進木は v1-v2-v3-v4-v5-v6-v7 と表される。

今の書き方を用いて、ヒープの条件の1を満たす「高さ2」の2進木をすべて表せ。

[ヒント]
高さ2のヒープの条件1を満たす2進木であるから、 条件「kを木Tの高さとする。Tでは深さk-1以下の可能な頂点はすべて使われ、 深さkの頂点は左から順に使われている。」は次のように読み替えられる。 ここでk=2である。 そこで、v4以外にどの頂点が使われているかを考えれば良い。

課題1-2

Binary Tee 左図の(1), (2), (3)それぞれについて問います。 これは二進木でしょうか、また強平衡二進木でもあるでしょうか、 さらにヒープの条件1を満たす二進木でしょうか? 理由をあわせて答えなさい。




[二進木、強平衡二進木、ヒープの関係]
強平衡二進木は名前が示すように二進木です。 またヒープの条件1を満たす二進木は強平衡二進木でもあります。 しかし、強平衡二進木の中にはヒープの条件1を満たさないものがあります。 この問題の(3)がその例です。

ヒープの条件2の検討

Binary Tee ヒープの条件の2は、木の頂点にそれぞれ数が格納されていることが前提となっています。 その上で、親頂点と子頂点のすべての組み合わせに対して、 親頂点をu、子頂点をv、頂点uに格納された数をf(u)、頂点vに格納された数をf(v)と表すと、 「f(u) ≥ f(v) 」が成り立つ、というのがこの条件です。

ここで、左図を見てください。 頂点の中に書いてある数(頂点のラベルとなっている数)が「頂点に格納された数」とします。 すると、(1)も(2)も根に格納された数は8、根の左の子頂点に格納された数は5、ということを表しています。

ここで、(1)と(2)は、ヒープの条件2を満たしているでしょうか?

(1)の二進木では、根に格納された数が8に対してその子頂点に格納された数はそれぞれ5(左の子)と7(右の子) ですから、8 ≥ 5 かつ 8 ≥ 7 となっています。これらに関しては条件を満たしています。 また根の左の子は子をもち、それに格納された数が3 ですから、5 ≥ 3となり、これも条件を満たしています。

以上から、(1)の二進木はヒープの条件2を満たしていると言えます。また、ヒープの条件1も満たしていますので、 ヒープであると言えます。

それに対して(2)の二進木はどうでしょうか?形は(1)と同じなのでヒープの条件1を満たしています。また、 頂点に格納された数からも(1)とほとんど同じです。ただ違いは、根の孫に格納された数が10であることだけです ((1)では3となっていました)。ここでその親頂点に格納された数が5なので、5 ≥ 10 とはなりません。 したがって、(2)はヒープの条件2を満たしていない、つまり(2)はヒープではないということになります。

課題1-3

下図のそれぞれの二進木に対して、ヒープであるかどうかを判定しなさい。またその判定の根拠も書きなさい。
Heaps


配列を用いたヒープの表現

今まで木はグラフとして図で示してきました。またコンピュータではリスト構造 (言い換えれば、ポインタを使ったデータ構造)として表してきました。

ところが、ヒープを容易に配列で表すことができます。 これはヒープの条件1によるものです。 この理由から、ヒープはリスト構造よりも配列で表すことが多いのです。 この考え方について学びます。

Heaps 左図は2進木を表しています。そして「可能な頂点」(つまり2進木の頂点として使われる可能性がある頂点)がすべて示されています。 ここで、頂点の番号を上から下に、左から右に番号をつけることを考えます。 つまり、まず根には1という番号を与えます。その子(深さ1の)頂点には、左から順に2、3という番号になります。 さらに根の孫に当たる(深さ2の)頂点には、左から順に4、5、...という番号がふられます。 (ここで深さkの頂点については、一番左の頂点は2**kという番号が、 そして一番右の頂点には2**(k+1)-1という番号がふられる、ということに注意してください)
これがヒープであるためには、 ヒープの条件1と条件2とを満たさなければなりませんが、 ここでは条件2は考えないこととして、条件1についてもう一度考えてみます。
条件1とは、「(木Tの高さをkとして) Tでは深さk-1以下の可能な頂点はすべて使われ、 深さkの頂点は左から順に使われている。」というものでした。 ここで高さ4の木を考えると、この条件1をみたすには、(k=4なので) 深さ3以下の可能な頂点はすべて使われていること、また深さ4の頂点は左から順に使われていることが必要です。左図の頂点の番号でいえば、v1〜v15までが使われ、深さ4の頂点である v16、v17、...は左の頂点から順に使われることになります。
Heaps このように、ヒープ(の条件1を満たす2進木)では、頂点はこの番号順に使われることになります。言い換えれば、どのヒープにおいても、最後の頂点の番号がmとすると、1〜(m-1)までの頂点は必ず使われていることになります。
そこで、木の頂点の番号と配列の指標とを対応付けることを考えましょう。 それを示したのが右図です。ただし配列の0番目は使わないこととします。すると、ヒープの番号aの頂点は、配列の指標がaの要素に対応します。このようにして、ヒープ(の条件1を満たす2進木)は、配列で表現されることになります。そして、配列の要素には、ヒープの頂点に格納された数が書かれます。




課題1-4

以下の要素をもつ配列は、どのような「ヒープの条件1を満たす」2進木に対応するか、 図を書いて示せ。またこれは「ヒープの条件2」を満たしてるか(つまりヒープを表しているか)?理由も合わせて答えよ。

  [nil, 30, 25, 28, 20, 24, 26, 18, 19, 11]

課題1-5

右図のようなヒープを配列で表現せよ。 Heaps









課題1-6

ヒープにおいて、根に格納された値(ヒープを配列で表した時の指標1の要素)は、他の頂点に格納された値のうちの最大のものと言えるだろうか?あなたの考えとそう考える根拠を述べよ。

課題1-7

ヒープを配列で表した場合、指標mの要素(頂点)の「親」頂点はどれか。「親」頂点の指標をmを用いて表せ。 また「左の子」と「右の子」が存在するとすれば、それらの頂点の要素はどれか。 mを用いて「左の子」頂点と「右の子」頂点の指標をそれぞれ表せ。


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