上篇對 binary tree 已有初步認識，這篇來介紹 max heap
與跟 max heap 相關的排序演算法 Heap Sort

Heap sort

• Heap sort use Max Heap to sort

So..What is Max Heap?

A max heap is a complete binary tree in which the value of a parent node is greater or equal to the values of its children.

最大堆積(max heap)就是 complete binary tree 其親節點的值均大於等於其子節點的值，而 root node 的值會是整個 tree 內最大的值

用圖片說明更清楚，以下就是一個 max heap 的 complete binry tree
root 的值為 17 為整個 tree 中最大的值

How to build Max Heap

首先先把 array 改寫為 tree
array[0] 對應 tree 1(也就是 root 的位置)
依序填入 binary tree 的格子中

假設 array 為 [17,27,52,12,4,13,5,8,23,11,6]
則 binary tree 會長這樣

Steps of build Max Heap

1. Start from each non-leaf node, beginning at the node at tree size/2(i.e., the last parent node)
   從 tree size/2 的位置（就是最後一個parent node）開始做 max-heap

2. Compare the parent node with its left and right children. If a child node is larger than the parent, swap them.
   將 parent node 跟 左右的 child node 做比較，如果 child node 大於 parent node 則交換彼此位置

3. After swapping, check if the subtree rooted at the swapped child node violates the max-heap property. If so, repeat the comparison and swapping for the affected subtree(i.e., heapify the subtree)
   當進行完 child node 跟 parent node 位置交換後，檢查以當下 child node 為 root 的 subtree 是否違背 max-heap，如果是，則對受影響的子樹執行 heapify(繼續往下層的 subtree 做比較與交換)

4. Continue the process for all non-leaf nodes. Once all substrees are heapified, the max heap is build.
   持續對每個 parent node 執行 heapify，直到所有的 substrees 都完成 heapified，max heap 即完成

這裡提供上方 array build max heap 的示意步驟

• 每個紅色方框所代表的是 sub-tree
  

Steps of Heap sort

1. Convert Array to Tree Structure
   Turn array into a complete binary tree.

2. Build Max Heap
   Start from the last non-leaf node, ensure the subtree rooted at each node follows the max-heap property. Continue this till the entire tree becomes a max heap(largest value at the root).

3. Swap Root with Last Element
   Swap the root element with the last element in the heap, reducing the heap size by one(since the last element is already sorted).

4. Rebuild the Max Heap

Complexity of Heap sort

O(n logn)

Implementation of Heap sort

相關資源

heap sort
https://www.javatpoint.com/heap-sort
Max Heap Data Structure Implementation in Java
https://www.digitalocean.com/community/tutorials/max-heap-java
heap sort
https://www.geeksforgeeks.org/heap-sort/?ref=header_outind
Heap - Max Heapify
https://www.youtube.com/watch?v=5iBUTMWGtIQ