アルゴリズムとデータ構造 --- 理論編 --- 山本 真基 ヒープソート アルゴリズムとデータ構造 --- 理論編 --- 山本　真基

ヒープの構築 --- アルゴリズムの説明 --- 1 2 3 入力：　0, 6, 3, 17, 9, 2, 10, 5, 11, 15 4 5 6 7 8 9 10 頂点番号（頂点の名前） 根付き二分木

ヒープの構築 --- アルゴリズムの説明 --- 入力：　0, 6, 3, 17, 9, 2, 10, 5, 11, 15 6 3 17 9 2 10 5 11 15 ラベルの付与 ラベル付き二分木

ヒープの構築 --- アルゴリズムの説明 --- 入力：　0, 6, 3, 17, 9, 2, 10, 5, 11, 15 6 3 17 9 2 10 5 11 15 ヒープ化：親が子より大！

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 9 2 10 5 11 15 まず，「始めの三点」 に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 9 2 10 5 11 15 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 15 2 10 5 11 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 15 2 10 5 11 9 次に，「隣の三点」 に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 15 2 10 5 11 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 15 2 10 5 11 9 最大のものは， 既に「三点の頂上」．

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 15 2 10 5 11 9 次に，「隣の三点」 に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 6 3 17 15 2 10 5 11 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 6 10 17 15 2 3 5 11 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 6 10 17 15 2 3 5 11 9 次に，「隣の三点」 に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 6 10 17 15 2 3 5 11 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 6 15 2 3 5 11 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 6 15 2 3 5 11 9 ここで，移動元の頂点が子をもつので，

ヒープの構築 --- アルゴリズムの説明 --- 17 10 6 15 2 3 5 11 9 その「配下の三点」に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 6 15 2 3 5 11 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 移動元の頂点に子がないので，

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 元の三点に戻る．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 次に，「隣の三点」 に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 ここで，移動元の頂点が子をもつので，

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 その「配下の三点」に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 17 10 11 15 2 3 5 6 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 2 3 5 6 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 2 3 5 6 9 更に，移動元の頂点が子を もつので，

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 2 3 5 6 9 その「配下の三点」に着目する．

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 2 3 5 6 9 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 9 2 3 5 6 最大のものを「三点の頂上」へ 移動する．

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 9 2 3 5 6 移動元の頂点に子がないので，

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 9 2 3 5 6 元の三点に戻る．

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 9 2 3 5 6 更に，元の三点に戻る．

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 9 2 3 ヒープ化完了！ 5 6 次に，「隣の三点」．．．， はない！

ヒープの構築 --- アルゴリズムの説明 --- 17 15 10 11 9 2 3 ヒープ化完了！ 5 6 つまり，どの親子も， 親が子より大！