# 演算法小考 0415
###### tags: `NCKU`
## Resource
- https://www.geeksforgeeks.org/heap-sort/
- https://rust-algo.club/sorting/heapsort/index.html
## 家任
## Heap Sort
https://rust-algo.club/sorting/heapsort/#build-heap-heapify
- Heap sort 將input轉換成一Complete Binary Tree, 利用max-heap或min-heap的最大(最小)值會出現在首個元素的性質去與最後一個元素替換來進行排序，其時間複雜度為$O(\log n)$。因為需要反覆進行n次所以得到$O(n \log n)$
- 上述流程Heapsort 最佳、最差的時間複雜度都一樣，得$O(n \log n)$

#include <iostream>
 
using namespace std;
 

void heapify(int arr[], int n, int i)
{
    int mx = i; 
    int l = 2 * i + 1;
    int r = 2 * i + 2;
 
    
    if (l < n && arr[l] > arr[mx])
        mx = l;
 
    if (r < n && arr[r] > arr[mx])
        mx = r;
 
    if (mx != i) {
        swap(arr[i], arr[mx]);
        heapify(arr, n, mx);
    }
}
 
void heapSort(int arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i=0; i<n; ++i){
        cout << arr[i] << " ";

    }
    cout << "\n";
 
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}
 
void printAll(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}
 
int main()
{
    int num;
    cin >> num;
    int arr[num];

    for (int i=0; i< num; ++i){
        cin >> arr[i];
    }
    
 
    heapSort(arr, num);    
    printAll(arr, num);
}

----

## vs6102085_馬廣辰
## Quiz1_pA
1. 將輸入的 records 建立為一個 Complete Binary Tree
2. 轉換成 Heap Tree (MAX HEAP)
3. 樹根是最大值，輸出樹根，並將二元樹中最後一個節點位置樹根中，最回到步驟二。如此步驟二、三反覆進行，可由大到小排序。

### 評估
Heap sort 的 best average, worst case 均為
$O(n \log n)$ 。假設 $2^{k-1} \le n \le 2^k$，因此二元樹之階度為 k 且第 i 階段之結點數為 $2^{i-1}$

在第一個 for 迴圈中，每個節點需要與子節點比較並做 Adjust 一次，此時費時是將每一個階度中節點數與該階度中之點點可能移動的最長距離的乘積累加起來，即
$\sum_{i \le i \le k}^{2^{i-1}} (k-i) = O(n)$

第二個 for 迴圈中，呼叫了 Adjust 程序 n - 1 次，且呼叫最高深度為 $k==[\log_2 (n+1)]$，因此此迴圈之費實為 $O(n \log n)$ 。因此，總共之計算時間 $O(n + n \log n) = O(n \log n)$。

## Quiz1_pB

假設以每個 group 有 5 個 elements 為例
第 1 步：將 𝑛 元素分成 5 個組。得到 ⌈𝑛/5⌉ 組。
第 2 步：找到每個 ⌈𝑛/5⌉ 組的中位數。
第 3 步：通過遞歸調用 SELECT 找到 ⌈𝑛/5⌉ 中位數的中位數 𝑥。 第 4 步：使用以主元元素為輸入的 PARTITION 的修改版本，圍繞 𝑥 對輸入數組進行分區。
第五步：考慮最壞的情況。
第 1 步：製作 5 個元素的組需要 O(𝑛) 時間。
第 2 步：在 O(1) 時間內對 ⌈𝑛/5⌉ 組進行排序。
第 3 步需要時間𝑇(⌈𝑛/5⌉)
第 4 步：圍繞 𝑥 對 𝑛 元素數組進行分區需要 O(𝑛) 時間。
步驟 5 需要時間 ≤ 𝑇(7𝑛/10 + 6)，假設 𝑇(𝑛) 單調遞增。


7 個一群：
$𝑇(𝑛) ≤ 𝑇 (⌈\frac {n}{7}⌉)$ + $𝑇(\frac {5n}{7} + 8)$ + O(𝑛) → θ(𝑛) => 𝑇(𝑛) ≤ θ(𝑛)

3 個一群：
$𝑇(𝑛) ≤ 𝑇 (⌈\frac {n}{3}⌉)$ + $𝑇 (\frac {2n}{3} + 4)$ + O(𝑛)→θ(𝑛 log 𝑛) => 𝑇(𝑛) ≤ θ(𝑛 log 𝑛)

---

## pC Find sum X - 紙筆測驗
1. 建立 map h1，key 為 A2 的所有元素
2. 建立一個 array targets，值為 Set A1 各個元素與 X 的差值
3. 遍歷 array targets 的 element，尋找 target 是否存在於 map h1 中，有則輸出此組配對

Time Complexity
1 => map 建立為 nlogn，取用為 O(1) => O(nlogn)
2 => O(n)
3 => 遍歷為 O(n)

因此 time complexity => O(nlogn)