重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下樹狀結構 Tree。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29814
本篇範圍：Chapter 6
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. Tree 是一種抽象的資料結構
2. 一定要有 root；每一個節點為 node (leaf)；node 之間稱為 edge
3. Tree 僅能有一個 root，因此不會是循環結構
4. Binary Tree 代表該樹最多僅有兩個子節點
Max Heap
1. Max Heap 必為近乎完整的 Binary Tree
2. 取任何一段 subTree，其根節點必為最大值
Heap Sort
1. Heap Sort 需要用到樹狀 Tree 的結構
2. heapSize 代表最後一個 index
3. 必須要先將原始 array 轉換成 MaxHeap
a. 任何一個 parentNode 為 i，則下方的兩個子節點的 index 為 2i+1 和 2i+2
b. 將這三個 node 的值進行比較後，若最大值所在的 index 跟原始的父節點不一樣，那就代表值要交換
c. 交換後，要執行遞迴檢查其交換後的下方所有子節點
4. 完成 MaxHeap 後，從陣列的最尾端跑一個 for-loop。由於最頂端都是 Max 值，所以這樣依序執行，將節點一個個從原始的 heap 除外後，最後呈現的結果就會是「由小到大」。
5. 換到 root 的值並不一定符合 MaxHeap 原則，所以要再呼叫「轉換成 MaxHeap」的方法
6. 時間複雜度為 nlogN。n 為 array 的長度；logN 為層數。
