４−３：高度なソートアルゴリズム�A （データ構造にもとづくソート）

内容

1. スライド　1 ４−３：高度なソートアルゴリズム�A（データ構造にもとづくソート）
2. スライド　2 ヒープソート
3. スライド　3 ヒープソートの方針
4. スライド　4 ヒープとは
5. スライド　5 ２分木
6. スライド　6 ２分木においては、左と右の子を区別するので、 次の２つの２分木は同一ではない。
7. スライド　7 木に関する用語
8. スライド　8 完全２分木
9. スライド　9 命題HP1（完全２分木と節点数）
10. スライド　10 （２）　（１）より、節点の総数は、次式で表される。
11. スライド　11 ヒープの形
12. スライド　12 ヒープ番号と配列での実現
13. スライド　13 ヒープにおける親子関係
14. スライド　14 証明
15. スライド　15 ：左子
16. スライド　16 ヒープにおける挿入
17. スライド　17 しかし、これだけだと、ヒープ条件を満たさない可能性 があるので、根のほうに向か...
18. スライド　18 挿入の例
19. スライド　19 ０
20. スライド　20 練習
21. スライド　21 ヒープにおける削除
22. スライド　22 しかし、これだけだと、ヒープ条件を満たさない可能性 があるので、葉のほうに向か...
23. スライド　23 削除の例
24. スライド　24 ０
25. スライド　25 ヒープソートの動き前半（ヒープへ値挿入）
26. スライド　26 ５
27. スライド　27 １
28. スライド　28 ヒープソートの動き後半（ヒープからの最小値削除）
29. スライド　29 ３
30. スライド　30 9
31. スライド　31 練習
32. スライド　32 ヒープソートの実現
33. スライド　33 命題HP３（ヒープソートの正当性）
34. スライド　34 ヒープソートの計算量
35. スライド　35 単一配列でのヒープソート
36. スライド　36 単一配列に変更する方針
37. スライド　37 ヒープ条件の変更
38. スライド　38 ヒープ化（ヒープソート前半）
39. スライド　39 配列
40. スライド　40 最大値の削除とソート
41. スライド　41 ヒープソート２の動き後半２
42. スライド　42 練習
43. スライド　43 単一配列ヒープの実現
44. スライド　44 単一配列ヒープソートの計算量
45. スライド　45 ヒープ化の高速化
46. スライド　46 ヒープ化の高速化におけるアィディア
47. スライド　47 イメージ
48. スライド　48 高速ヒープ化の動き
49. スライド　49 1
50. スライド　50 0
51. スライド　51 void heap_sort() { int i; ...
52. スライド　52 命題HP４（高速ヒープ化の最悪時間計算量）
53. スライド　53 このことより、ヒープ化に必要な最悪計算時間量を と書くと次式が成り立つ...
54. スライド　54 スライド54
55. スライド　55 ヒープソートの計算量