# 第八週課程內容 (2018/10/19)

進階的資料結構大部份和 tree 有關，
如果還不夠熟悉，建議先複習一下上週內容。

# heap

heap 用於快速取得極大/極小值，可以想像成把東西堆成一座小山，
山頂永遠是極大（或極小）值，但山頂外都是散亂的。

山頂是極大值稱為 max-heap，極小值稱為 min-heap，
以下以 min-heap 為例，max-heap 除了比較方式不同之外，其餘完全相同。

heap 有以下幾種可能操作：

- 詢問極值：O(1)
- 取出極值：O(log n)
- 放入一個新的東西：O(log n)

heap 會是一棵 complete binary tree，
且滿足「任意 node 皆小於左、右 children」的特性。
根據遞移律，任意 node 會小於任何左子樹、右子樹中的所有 node，
因此 root 保證小於這樹中任何其它 node，故極小值必存在於 root。

但這特性並不保證左右子節點的大小關係，因此除了極小值外，其餘皆無法確定。

## heap implement

基於 complete binary tree 的特性，heap 通常以陣列標記的方式實作。
root 會落在 index 1 的位置，這也是極小值所在位置。

## insertion && heap up

對 n 個 node 的 heap 新增 node 的時候，
我們會把新 node 放在 n+1 的位置，這位置肯定是 leaf。
此時唯一有可能不符合 heap 定義的地方，只有新加入的 node。
此 node 有可能比它的 parent 來得小，因此需要做 heap-up 的調整：

如果新 node 比 parent 小，則將它與 parent 交換；
反覆此動作至新 node 比 parent 大，或者新 node 成為 root 為止。

調整後，此 heap 會維持「任意 node 皆小於左、右 children」的特性。

## deletion && heap down

對 n 個 node 的 heap 拔除極小值（root）的時候，
root 為空，為了維持 complete binary tree 的特性，
將最後一個節點（位置 n）放到 root，這時維持 complete binary tree 的特性。

但此時的 root 可能不是極小值，因此需要做 heap-down 的調整：

如果此 node 比「最小的 children」大，就和「最小的 children」交換；
反覆此動作至此 node 比「最小的 children」小，或者成為 leaf 為止。

調整後，此 heap 會維持「任意 node 皆小於左、右 children」的特性。

## make heap

要將 n 個節點建成 heap 有兩種方法：

- 方法一：從位置 1 開始，依序對每個點做 heap-up，複雜度：O(n log n)
- 方法二：從位置 n 開始，依序對每個點做 heap-down，複雜度：O(n)

方法一等同於將 n 個點依序插入，每次插入 log n 總合是 n log n。
方法二則是從 leaf 開始先建成很多個 heap 再慢慢合併成一個。

方法一在最糟的最下層，也就是 leaf 那層最差有 n/2 個點，
每個點最差是往上浮到 root，也就是 log n。

方法二最下層本來就只有一個點，本來就是一棵 heap，
在最糟的往下沉到 leaf 的 log n 的情況，只有 root 一個點。
計算量是：

- 最下層（n/2個）直接忽略（0）
- 次下層（n/4個）最差下沉 1 次（n/4）
- 再來（n/8個）最差下沉 2 次（n/4）
- 再來（n/16個）最差下沉 3 次（約n/5）
- 再來（n/32個）最差下沉 4 次（n/8）
- 再來（n/64個）最差下沉 5 次（約n/12）
- ...

由此可知計算量會逐層收斂至 root 的 log n 次，
而上面這最大的 6 層，只取大概（但保證比實際值大）也只有約 0.91 * n 的程度。
因此方法二的複雜度僅為 O(n)。

## heap delete && update

要刪除 heap 中非 root 的節點並非易事，
為此我們通常不直接刪除點，而是加上「已被刪除」的標記。

一旦判斷新拿出來的 root 被標記為「已被刪除」，就不要處理它。

同理，要「改變」裡面某個值，同時維持 heap 特性也是十分困難的事，
為此通常會把「新的值」扔進 heap，把「舊的值」標記為「已被刪除」。

## heap sort

先將 n 個點建成 heap（複雜度 n），再依序拿出每個點（複雜度 n log n），
即可把 n 個點由小到大排序。

不過沒有特別好處，沒有 quick sort 快，只是可以這樣用而已。

## 雙 heap

雙 heap 用在想找第 k 大的值，
但是有可能途中會再加入新的值，加入後再找第 k 大的情況。

儘管插入時，和第 k 大比較可馬上知道第 k 大有沒有換人，
但不維持排序狀態也無法確定要換成誰。
每次重新排序需要 n log n 的時間，
插入排序法每次插入需要 n 的時間。

這時我們可以建立一個長度 k 的 max-heap，
以及一個長度 n-k 的 min-heap。
則 max-heap 的 root 即為第 k 大，
min-heap 的 root 即為第 k+1 大的值。

插入新的點的時候：如果比當前第 k 大還大，就往 min-heap 塞；
如果比當前第 k 大還小，就把 max-heap 的 root 往 min-heap 塞，
再把新的點塞到 max-heap。

如此只要 log n 的時間，就可以重新找到第 k 大的數是誰。

## priority queue

priority queue 是一種允許插隊的 queue，
每個點會被給予一個「優先度」，每次拿出一個點時，「優先度」最高的點，
會最先被拿出來。

由於每次對「優先度」取極值，因此可用 heap 實作。

# disjoint set

disjoint set 可以讓你將任意兩個人所在的集合合併成一個集合，
或問你兩個人是否屬於同一個集合。

例如：告訴你 a 和 b 是朋友，b 和 c 是朋友，且朋友的朋友也是朋友，
問你 a 和 c 是不是朋友。

把所有集合看成組織，推出一個「老大」代表整個組織。
除了「老大」以外，每個人都有剛好一個直屬上司。

這樣對任何人，只要循著上司往上追，就能夠追溯到最上層代表組織的「老大」，
就可以知道他所在的組織。


如果兩個人擁有同一個「老大」，則表示此兩人同屬一個組織。

如果告訴你 a 和 b 所在組織被合併成同一個組織，
那麼只要讓 a 的「老大」臣服於 b 的「老大」（或者相反）即可合併：


如此一來，a 和 b 便被合併至同一組織，擁有共通的「老大」。

## 路徑壓縮

從詢問過程中可以發現：上司一點都不重要，最重要的是找出最後的「老大」。
因此，在詢問上司的過程，可以將所有遇到的人都直接把上司改成「老大」，
可減少下次問出「老大」所需的詢問次數。


注意：圖中並未指向真正的（左邊「老大」）「老大」，
是因為「詢問 b 的老大」這件事發生在「合併」之前，
因此路徑壓縮也發生在「合併」之前。

# binary search tree

binary search tree 是一棵 binary tree，對任意 node 滿足以下條件：

- left sub-tree 全部比自己小
- right sub-tree 全部比自己大

由以上特性可知：中序（左中右）走訪所得到的順序，即為所有 node 的排序結果。


理論上，每次詢問一個值存不存在，只需要 log n 的時間；
但如果傾斜，最差會劣化至線性時間。


## insert

插入一個新的節點時，從 root 出發，
由定義可知：如果它比 root 大，則應插在右子樹；
如果比 root 小，則應插在左子樹。

由此遞迴至應該插的子樹（左子樹或右子樹）為空，就把它放上去。


## 刪除

刪除的方法相當複雜，因此通常在找出要刪除的目標後，
只會將它標記為「已被刪除」。

刪除的實作方法：

- 如果左子樹（或右子樹）為空：把另一邊子樹往上提


- 如果左子樹、右子樹皆不為空：找到左子樹最大值取代自己，然後刪除


左子樹中最大者，同樣滿足「比左子樹所有 node 大」且「比右子樹所有 node 小」，
因此可以拿來取代自己；又因為它是左子樹中最大者，故右子樹必為空。
右子樹為空，就可以按照上面方法刪除，拿左子樹取代自己位置。

## 找第 k 大的點

對每個點記錄自己「左子樹（含自己）有多少個點」，在每次插入新點時更新；
例如要找第 20 大的節點：

- 若左子樹（含自己）節點數 = 20 => 自己就是第 20 大
- 若左子樹（含自己）節點數 > 20 => 找左子樹中第 20 大
- 若左子樹（含自己）節點數 < 20（例如 16） => 找右子樹中第 20-16 = 第 4 大

## 平衡樹

binary search tree 最大的問題就是在傾斜，
因此有幾種讓它維持平衡不傾斜的方式，最著名的就是紅黑樹。

由於實作複雜、困難，又通常有替代案存在，
在競賽中使用通常會陷入不利的情況，在此略過不提。
有興趣可以自行用關鍵字找資料閱讀。

# 作業

以這些進階資料結構為主。

當中也存在一些暴力法同樣能夠 AC 的題目，但還是希望大家嘗試正規解法。

[SkyOJ 連結](http://sky.tfcis.org/rank.php?mod=commonboard&id=74)

- UVa501
- UVa793
- UVa10107
- UVa10583
- UVa10608
- UVa10954
- UVa12347

## 建議

有些題目 Lucky貓 沒有中譯，
需要閱讀原文題目，若閱讀上有困難可以到 FB 社團尋求同學協助。

## 給資訊社競賽組的作業

:::warning
非資訊社競賽組的同學們可以無視這部份。
當然也歡迎挑戰，雖然可能會十分吃力，
並且可能會需要你們完全沒學過的技能與知識。
:::

同樣不定型，但…
解禁 flow 和 flow 相關題。

[SkyOJ 連結](http://sky.tfcis.org/rank.php?mod=commonboard&id=75)

- UVa240
- UVa258
- UVa399
- UVa563
- UVa10080
- UVa10307
- UVa10720
- UVa11504
- UVa11506
- UVa11987

###### tags: `APCS2018上`