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

Presentation on theme: "アルゴリズムとデータ構造 --- 理論編 --- 山本 真基"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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