ヒープソートの復習 第12回
ヒープソート(heap sort)(p.94) ※ ヒープを用いてデータの整列を行うアルゴリズム 計算量 O (n log n) ヒープ : 配列により半順序木を実現したもの 常に子が親より 大きい木の例 常に子が親より 小さい木の例 3 10 5 9 8 9 6 8 9 10 6 3 7 6 10 18 9 4 1 2
ヒープソートの原理 ※ リストＬ ２，９，５，６，… １．ヒープ（半順序木）を作る（優先度つき待ち行列に入れる） ２．以下の処理を繰り返して並べかえる ヒープの先頭の要素と末尾の要素を交換 [先頭]～[末尾-１]の部分の半順序を回復させる 優先度つき 待ち行列 リストＬ ２，９，５，６，… ９ ６ ５ ２
１．ヒープを作る 部分木の根の要素を適切な位置まで下げる操作を繰り返すことで，半順序木をボトムアップに構築する 10 6 9 5 15 15 ← a[0] 要素数 n = 15 6 9 5 15 15 12 ← a[n/2-1] (=a[6]) 3 18 9 8 11 9 20 10 ← a[n-1] (=a[14])
２．並べかえ ２－１ 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 ２－１ 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 15 11 3 20 [0] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 3
着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある ２．並べかえ（つづき） この部分の 半順序を 回復させる ２－１ 残りの部分の半順序の回復 10 5 6 8 9 18 12 15 11 3 20 子が親より小さい間， 2つの子のうち 小さい方の子 と親を交換していく この部分のヒープを再構成 [0] [1] [2] [3] [4] [7] [8] [n-2] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 5 12 6 10 3 着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある
プログラムの概要 １．ヒープ（半順序木）を作る ２．以下の処理を繰り返す begin heapsort ヒープの先頭の要素と末尾の要素を交換 トップダウンに[先頭]～[末尾-１]の部分の半順序を回復させる heapsort heapify downMin deleteMin downMin end