## HW5

1. Heap Sort
1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程。

    digraph dg{
        44 -> 42;
        44 -> 35;
        42 -> 33;
        42 -> 31;
        35 -> 19;
        35 -> 27;
        33 -> 10;
        33 -> 26;
        31 -> 14;
    }

- Ans:
1. 去掉最大元素

            digraph dg{
                14 [style=filled, fillcolor= "#FFCF76"]
                14 -> 42;
                14 -> 35;
                42 -> 33;
                42 -> 31;
                35 -> 19;
                35 -> 27;
                33 -> 10;
                33 -> 26;
            }

2. 找 14/42/35 之間最大的元素後交換

            digraph dg{
                14 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 -> 14;
                42 -> 35;
                14 -> 33;
                14 -> 31;
                35 -> 19;
                35 -> 27;
                33 -> 10[weight=0.5];
                33 -> 26[weight=0.5];
            }

3. 找 14/33/33 之間最大的元素後交換

            digraph dg{
                14 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                33 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 -> 33;
                42 -> 35;
                33 -> 14;
                33 -> 31;
                35 -> 19;
                35 -> 27;
                14 -> 10[weight=0.5];
                14 -> 26[weight=0.5];
            }

4. 找 14/10/26 之間最大的元素後交換

            digraph dg{

                26 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 -> 33;
                42 -> 35;
                33 -> 26;
                33 -> 31;
                35 -> 19;
                35 -> 27;
                26 -> 10[weight=0.5];
                26 -> 14[weight=0.5];
                14 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
            }

2. 投影片69頁的公式如下，請解釋此公式的含意。

2. Problem平均的Lower Bound
- 從0開始的結果:

3. Problem Transformation
- Sorting problem reduces to Convex Hull Problem
- 請說明，若要排序五個數字：4,1,3,2,5，如何轉為Convex Hull Problem後，完成排序。

reference:

1. [Graphviz note](https://hackmd.io/9yNZus8GTFaeHjjwcv_CBQ?both)
2. [Attributes Color](https://hackmd.io/@eric88525/graphviz-note)
3. [Attributes Color](https://hackmd.io/@lilybon/graphviz)