# Lecture 07 - Heap sort
> 課程內容 : 中興大學資工系 范耀中教授 (112 學年度第 2 學期)
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## 1. Question
> **Top M question :**
> Given a sequence with n number, then choose the largest M number.

假設一組數列 : 100, 2, 30, 4, 22, 88, 28, 11, 19, 20, 30, 50, 5, 7, 1000，要從其中挑出最大的 5 個數字

### 1.1 Solution (1) : unordered method
以 unordered method 的方法來說，挑選過程中不需要時刻保持長度為 m 的序列的內部數字的大小順序，具體過程如下 :

* 將序列的數字依序往左放入長度為 5 的陣列中
* 陣列塞滿後，從陣列左側放入並開始比較
* 遇較大的數，向後(右)移動
* 欲較小的數，取代，且取代的數字往後繼續比較

| Step | Insert | $a_1$ | $a_3$ | $a_3$ | $a_4$ | $a_5$ |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 1 | 100 | 100 |
| 2 | 2 | 100 | 2 |
| 3 | 30 | 100 | 2 | 30 |
| 4 | 4 | 100 | 2 | 30 | 4 |
| 5 | 22 | 100 | 2 | 30 | 4 | 22 |
| 6 | 88 | 100 | **88** | 30 | 4 | 22 |
| 7 | 28 | 100 | 88 | 30 | **28** | 22 |
| 8 | 11 | 100 | 88 | 30 | 28 | 22 |
| 9 | 19 | 100 | 88 | 30 | 28 | 22 |
| 10 | 20 | 100 | 88 | 30 | 28 | 22 |
| 11 | 30 | 100 | 88 | 30 | 28 | 22 |
| 12 | 50 | 100 | 88 | **50** | 30 | 28 |
| 13 | 5 | 100 | 88 | 50 | 30 | 28 |
| 14 | 7 | 100 | 88 | 50 | 30 | 28 |
| 15 | 1000 | **1000** | 100 | 88 | 50 | 30 |

因為有 n 個數字要填入，且每個數字都需要比較 m 次，因此時間複雜度為 $N \times M$

### 1.2 Solution (2) : ordered method
另一種 ordered 的方法，在挑選過程中隨時會保持陣列中的大小順序，具體過程如下 :

* 從右側填入
* 填入數字檢查
* 比右側數字大，交換
* 比右側數字小，不變
* 陣列填滿後從左側插入數字繼續做比較

| Step | Insert | $a_1$ | $a_3$ | $a_3$ | $a_4$ | $a_5$ |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 1 | 100 | | | | | 100 |
| 2 | 2 | | | | 2 | 100 |
| 3 | 30 | | | 30 | 2 | 100 |
| 4 | | | | **2** | **30** | 100 |
| 5 | 4 | | 4 | 2 | 30 | 100 |
| 6 | | | **2** | **4** | 30 | 100 |
| 7 | 22 | 22 | 2 | 4 | 30 | 100 |
| 8 | | **2** | **22** | 4 | 30 | 100 |
| 9 | | 2 | **4** | **22** | 30 | 100 |
| 10 | 88 | 88 | 4 | 22 | 30 | 100 |
| 11 | | **4** | **88** | 22 | 30 | 100 |
| 12 | | 4 | **22** | **8** | 30 | 100 |
| 13 | | 4 | 22 | **30** | **88** | 100 |

後面依此推類，因為過程中永遠都會保持陣列中的順序，所以稱為 ordered method。Best case 的時間複雜度為 N，worse case 的時間複雜度為 N×M。

這樣的問題，其實可以用 heap sort 來完成，

> Heap sort 可以說是理論上最完美的 sorting

## 2. Review : heap
Heap 有 5 個主要的核心概念，以下簡述之

### 2.1 Core concept (1)
> Heap must be a complete binary tree

Complete tree 的概念有二 :

* 除了最後一層外，所有的 node 都必須是滿的
* 最後一層的 node 需由左至右依序填滿


### 2.2 Core concept (2)
> Parent node's values always larger than its children


### 2.3 Core concept (3)
> Heap can use an array to implement

任何的 heap 都可以用一個陣列來實作，以下圖的 complete binary tree 為例


使用 array 實作後可得 $[-, 100, 88, 7, 87, 65, 3, 4, 2]$，
其中開頭的第一項為了計算方便，所以不填值

### 2.3 Core concept (4)
> Tree traversal can be done by simple math :
> * For children of node $i$ : $2i$ or $2i+1$
> * For parent of node $i$ : $\lfloor \cfrac{i}{2} \rfloor$

以上述的陣列與 binary complete tree 的 3 號節點(數字 7)為例，3 號節點的 children node 為 6 號與 7 號節點

$$
\begin{align}
2 \times 3 = 6\\
2 \times 3 + 1 = 7
\end{align}
$$

3 號節點的 parent node 為 1 號節點

$$
\lfloor \frac{3}{2}\rfloor = 1
$$

### 2.4 Core concept (5)
> Two operation : insert and delete

以下圖的 binary complete tree 為例，欲在 9 號位置 insert一個 node


##### Insert
通常是新增節點到最後一個位置，如下圖，新增 9 號節點後開始力爭上游往上比較，遇到較小的數字就做交換，值得沒得換為止，這個動作稱為 swim up


##### Delete
通常是刪除根節點，有以下幾個步驟


* 先把根節點 pop 出來
* 把最小的節點往上移動
* 第 2 層的 node 互相比較，較大的再跟 i = 1 的 node 交換
* 繼續比較，直到無法下沉為止

這個動作稱為 sink down

## 3. Complete binary tree
以 complete binary tree 來說，假設有 n 個節點，則樹的高度為 $\lfloor \log_2 N\rfloor$，且 delete 與 insert 的時間複雜度都是 $\log_2 N$，因為有 N 個 layer 需要做比較。

此外，從 delete 的過程可以發現到下沉(sink down)的順序其實就是排序大小的順序