ヒープソート

二進木とは 木はグラフの特殊なものである。 木とは「根」と呼ばれるただ一つの頂点（節点、ノードともいう）と 　それに接続する頂点、頂点と頂点をつなぐ枝(アークともいう）から 　構成される 図示すると

２進木 根 枝で接続された２つの頂点のうち、上にあるものを「親」、下にあるものを「子」という 深さ０ 深さ１ 深さ２ 枝で接続された２つの頂点のうち、上にあるものを「親」、下にあるものを「子」という 頂点の深さとは、根からその頂点までの枝の個数のこと 2進木：　どの頂点もその子の個数は高々2個に限られる木 子は親頂点に対し「左の子」「右の子」と呼んで区別する

高さ 2 の二進木 (1) (2) (3) (5) (6) (4) (8) (9) (7) (10) (11) (12)

高さ 2 の二進木(続き） (13) (14) (15) (16) (18) (17) (21) (19) (20)

ここで考える「木」 頂点に「数値」が記憶されている 頂点を u で表すと、記憶された数値は f(u) で表す 頂点と頂点の間の枝、ある方法で指定される（後述）

｛ ｛ 配列を用いた２進木の表現 ｛ 図による二進木 … … 配列による表現 ① ② ③ ⑤ ⑥ ⑦ ④ ⑨ ⑧ 1 根 2 深さ１ 3 4 ① 1 根 根以外は ｛ 2 偶数： 左の子 深さ１ 3 ② ③ ｛ 4 奇数： 右の子 ⑤ ⑥ 深さ2 ⑦ 5 ④ 6 ⑨ 7 ⑧ ｛ 8 深さ3 9 図による二進木 … … 配列による表現

ヒープ 親 子 ヒープ(heap)とは、特殊な二進木 定義　高さkの二進木Tがヒープであるための必要十分条件は次の (i), (ii)を満たすこと 　(i) 深さ0 ～ k-1 の可能な頂点はすべて使われ、 深さkの頂点は左から順に使われている 　(ii) 頂点uが頂点vの親なら 　　 uの値( f(u) ) ≧ vの値( f(v) ) この条件は「配列」で2進木を表すと、わかりやすい 親 子

｢可能な頂点」と｢使われている」 「可能な頂点」は3個 (1) (2) 高さ 1 の二進木を考える ① 木の頂点になりうるもの ② ③ ① 実際に木の頂点になっている (1) (2) ① ① ③ ② ①と②が使われ③は使われていない ①と③が使われ②は使われていない

｛ ｛ 配列を用いたヒープの表現 ｛ 二進木による表現 … … 配列による表現 ① ② ③ ⑤ ⑥ ⑦ ④ ⑨ ⑧ ① 1 根 根以外は ｛ 2 偶数： 左の子 深さ１ 3 ② ③ ｛ 4 奇数： 右の子 ⑤ ⑥ 深さ2 ⑦ 5 ④ 6 ヒープの条件(i)は配列表現において、 １から順に要素が入っている、ということ ⑨ 7 ⑧ ｛ 8 深さ3 9 二進木による表現 … … 注目：深さkの一番左の子の番号は 2k 配列による表現 それでは一番右の子の番号は ?

ヒープの特徴 二進木 1 頂点の番号のつけ方： 上から下、左から右 3 2 6 7 4 5 9 8 10 この番号の付け方から、高さ n (> k)のヒープでは、 ★深さ k の最も左の頂点の番号は 2k ★深さ k の最も右の頂点の番号は 2(k+1) - 1

ヒープの演習 ヒープの条件(i)を持つ 高さ２、頂点数6の二進木 を書け 高さ３、頂点数 11 の二進木 を書け 高さ２、頂点数6の二進木　　を書け 　　　高さ３、頂点数 11 の二進木　を書け 定義　高さkの二進木Tにおいて (i) 深さ0 ～ k-1 の可能な頂点はすべて使われ、 深さkの頂点は左から順に使われている

ヒープの演習（続） ３. 右の配列に対応 する二進木を書け。 ただし、ヒープを配 列で表す規則に従 うとする。 　ただし、ヒープを配 列で表す規則に従 うとする。 　これはヒープの条 件を満たしている か？ 1 30 2 25 3 28 4 20 5 24 6 26 7 18 8 19 9 11 10 11

ヒープの演習（続） ４. 以下の二進木に対応する配列をかけ。ただし、ヒー プを配列で表す規則に従うとする。これはヒープの条 件をすべて満たすか？ 20 10 15 4 7 11 6 1 5 2 3

ヒープへの要素の追加(挿入)手続き 手続き：以下の2ステップで行う 新たな要素を値とする頂点をヒープに追加 ⇒ 条件(i)を満たすところに (2) 次に、ヒープ条件(ii)を満たすように修正する 定義　二進木Tにおいて (ii) 頂点uが頂点vの親なら 　　 uの値≧ vの値

ヒープへの要素の追加(1) 8 5 7 3 10 例： に3を追加する… それには、ここしかない さらに、 10を追加する。。。 　　　　　　　　　　　　　　に3を追加する… 定義　二進木Tにおいて (ii) 頂点uが頂点vの親なら 　　 uの値≧ vの値 8 5 7 それには、ここしかない 3 そして、ヒープ条件(ii)を満たしているのでヒープが完成 10 さらに、 10を追加する。。。 これは、ヒープ条件(ii)を満たしていないので『修正』が必要

ヒープへの要素の追加(1)続き ヒープの条件(i)を満たすように要素を追加する ことは、 (b)二進木で表す場合、｢可能な頂点を左から順に使う」 (a) 配列で表す場合は分かりやすい 　　⇒　ヒープの最後の要素のインデックスを x とすれば、x+1 番目に要素を追加すれ 　　　　ばよい

ヒープへの要素の追加(2)「作り直し」 追加した頂点を v とする ヒープの条件(ii)は、 親頂点の値≧子頂点の値 　　　　親頂点の値≧子頂点の値 　だから、これが満たされていればOK. 　そうでなければ、上の条件を満たすように、頂点を入れ替えていく （作り直しする）

ヒープへの要素の追加(2)続き ヒープへの要素の追加の完成 8 条件を破っている 5 7 条件を破っている 3 10

具体的に例を用いてヒープを作る 8 入力データ: { 8 5 7 3 10 5 7 9 6 1 20 } ヒープ条件(ii)を破っているので、『作り直し』が必要 3 10 9 6 1 20 問題:　ヒープ条件(ii)が成り立つようにするには、どのように『作り直し』したらよいか？

ヒープソート(Heap Sort) ヒープを用いてソート（並び替え）を行う 手続き： (1) x1, x2, …, xn からヒープ(木)を作る 　　　計算量は O(n * log n) 　　　ヒープ木においては根が最大の値の頂点 (2) 根と『最も深い頂点のうち最も右端の頂点』とを交換し、『根だった 頂点をヒープから切り離し』てからヒープを作り直す。この操作一回 ごとの計算量は O(log n) (3) (2)を繰り返し、切り離された頂点をすべて並べるとソート完成(新し く切り離された頂点が最小、古いものが最大)

ヒープソート(続き) 20 10 9 5 8 7 6 3 1 ≧ ≦ ヒープの作り直し(ヒープソートのステップ(2)) 1. 根と『最も深く右側の頂点』とを交換し、根だった頂点を切り離す 20 2. ヒープ条件(ii)を満たすよう、ヒープを作り直す 10 9 ≧ 親頂点と、子頂点のうち大きいほうを交換。 5 8 7 6 ≦ 3 1 問題：　ヒープをどのように作り直すか？ 問題：　この後ヒープをどのように作り直すか？

ヒープソートの真髄 ヒープを配列で表わす ⇒『木』よりも簡単なデータ構造で実行可能 インデックスによって、根の頂点を簡単に求めることができる 　　⇒『木』よりも簡単なデータ構造で実行可能 インデックスによって、根の頂点を簡単に求めることができる また、注目している頂点のインデックスから、その親や子の頂点が何か が簡単に計算できる 問題：　注目している頂点のインデックスをxとすると、その親と子の頂 点のインデックスは？

演習問題 配列を用いてヒープソートするプログラムを作る。 入力データからヒープ(配列で表現)を作る関数makeHeapを作れ makeHeap(int a[], int h[], int n) : 配列a（n個の要素）からヒープの配列hを作る ヒープhのインデックス番号iとjの要素を交換する関数swapNodesを 書け： swapNodes(int h[], int i, int j) 最後の要素のインデックスを x とすると、 1～(x-1) までの要素を ヒープに作り直すコード（remakeHeap)を書け remakeHeap(int h[], int x)---配列hは、できていたヒープに対し、根 (h[1])と最後の要素h[x]を入れ替えた状態である。 (4) 以上を組み合わせて、ヒープソートを行う関数(heapSort)を書け 　　heapsort(int a[], int h[], int n) --- aが入力、要素数がn。h[1]～h[n]が ソートされた配列となるようにする： makeHeap, swapNodes, remakeHeapを使う