## 資結筆記｜堆積樹（Heap Tree）

### 複習
  上次提到了[二元樹（binary tree）](https://hackmd.io/@fooox0864/HyYpYIqTyg)，如果還沒有看或是感興趣的讀者可以去看看唷！

<br/>

### 基本概念

基本上堆積樹（heap tree）屬於完全二元樹的一種，常用於找極值，有兩種堆積的方法如下

<br/>

#### 最大堆積樹（maximum heap）

根節點的值是所有節點中最大值，每個父節點的值一定大於等於子節點的值。

#### 最小堆積樹（minimum heap）

根節點的值是所有節點中最小值，每個父節點的值一定小於等於子節點的值。

以上不論是最大還是最小堆積樹，同一層的值大小皆不需理會

<br/>

### 建立堆積樹

一開始第一個值放在根節點，接著由左而右插入節點，當一層滿了則在往下一層建立新的節點，接著檢查有子節點的父節點進行調整，見下圖

假設以 10 21 5 9 13 28 3 建立最小堆積樹為例

（1）先依上述規則練利一棵樹，接著檢查有子節點的節點，有節點10、節點21、節點5，檢查的順序要跟建樹的順序反過來為5->21->10

（2）因為節點5>節點3，故交換
（3）因為節點21>節點9，故交換
（4）因為節點10>節點3，故交換
（5）因為節點10剛剛交換有動到這個節點所以再檢查一次，節點10>節點5，交換

以上是建立最小堆積樹的方法，建立最大堆積樹就是反過來就可以囉～

<br/>

### 新增節點
新增一個節點，就依照建立堆積樹的規則插入左下角，然後再做比大小調整順序就可以了

<br/>

### 取出堆積樹的極值
將根節點的值取出放入序列，將右下角的節點放到根節點的位置，接著一樣進行比大小然後調整位置。

以上是堆積樹的基本概念，實作的部分有機會再跟大家補充