# Heap Sort 堆積排序法 + 一種以 `Tree` 的資料結構其中的 Max Heap 作為整個演算法的主要概念，Max Heap 是 Tree 的一種。 + 先將陣列想辦法變成 Max Heap，並再完成排序。 *** ## 目錄 - Tree 資料結構 > Tree > Binary Tree > Full Binary Tree > Complete Binary Tree > Max Heap - Heap Sort 流程 - 介紹 - BigO - 為什麼是 O(nlogn) ? - 參考資料 *** ## Tree 資料結構 樹（Tree）是一種無順序的資料結構，方便快速找資料。為什麼會叫 Tree，因為這種資料結構像極倒過來的樹 以下是 Tree 的特性，結點又稱為 Node + 樹根結點 (root)：就是最頂端的結點，每個 tree 只會有一個 root + 子樹 (child tree)：由結點和其後代構成 + 子結點 (child node)：有父結點的結點，所以基本上除了 root 都是 + 葉結點或稱外部結點 (leaf)：沒有子結點的結點，也就是最底端的結點 + 結點深度 (depth)：祖先結點數量 + 樹的高度 (height)：最大深度到第幾層 `以下介紹常見的 Tree ` &emsp;      *** ## Heap Sort 流程 一袋米要扛幾樓 o.O          ``` python def buildMaxHeap(heapSize): for i in range(int(heapSize/2),-1,-1): maxHeapify(i, heapSize) def maxHeapify(i, heapSize): left = i * 2 +1 # 結點左下 index right = i * 2 +2 # 結點右下 index if left <= heapSize and arr[left] > arr[i]: largest = left else: largest = i if right <= heapSize and arr[right] > arr[largest]: largest = right # 要把 arr[i] 往下換，largest 在下面 if largest != i: arr[i], arr[largest] = arr[largest], arr[i] maxHeapify(largest, heapSize) def heapSort(arr): heapSize = len(arr) - 1 buildMaxHeap(heapSize) for i in range(len(arr)-1,-1,-1): # root 與 arr[i] 交換 arr[0], arr[i] = arr[i], arr[0] heapSize -= 1 maxHeapify(0, heapSize) return arr arr = [5, 23, 16, 0, 3, 9, 87] print(heapSort(arr)) # [0, 3, 5, 9, 16, 23, 87] ``` ## 介紹 使用到 3 個函式，分別為 &nbsp;&nbsp;**buildMaxHeap** &nbsp;&nbsp; **maxHeapify** &nbsp;&nbsp; **heapSort** `buildMaxHeap` 是一開始將混亂的 tree 逐步調整成 Max Heap `for i in range(int(heapSize/2),-1,-1)` 代表從最右下角的三角形開始 一路到最上層的三角形，都去執行 `maxHeapify`，也就是將 largest 值往上搬的動作 在 `heapSort` 函式中，因為 for 從 len(arr) 到 -1，代表 i 是從陣列尾到頭 又因為每次 `maxHeapify` 後 a [ 0 ] 會變成 root (最大值) 並與 a [ i ] 互換，所以就會從尾巴開始放大的值，一路到最小 `Heap Sort` 就是以上邏輯，非常之複雜 :) ## BigO Worst Case Performance: O(nlogn) Best Case Performance: O(nlogn) Average Performance: O(nlogn) ## 為什麼是 O(nlogn) ?  &emsp; 由上圖所示，`maxHeapify` 的運作 BigO 值為 O(logn)，代表含義是如果今天要從頂端換到最底，要換幾次才能到達 `heapSort` 與 `buildMaxHeap` 都可以當是 O(n) 又因為 `maxHeapify` 在他們裡面，所以要相乘，得出 Heap Sort 的 BigO 值就是 **O(nlogn)** *** ## 三個字 超級複雜 :( *** &emsp; ## 參考資料： [[資料結構] 樹Tree - Medium](https://medium.com/starbugs/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E6%A8%B9-tree-1cfddf5685ce) [Binary Tree: Intro(簡介)](http://alrightchiu.github.io/SecondRound/binary-tree-introjian-jie.html) [Day21:[排序演算法]Heap Sort - 堆積排序法 - iT 邦幫忙](https://ithelp.ithome.com.tw/articles/10266206) Udemy - 資料結構與演算法 (JavaScript)