堆積排序

習題預習

1. Heap Sort是怎麼運作的？他的時間複雜度是多少？
2. 如何建立一個Heap，並且將其改成最小堆或最大堆？
3. 如何在Heap Sort中進行排序，可以避免過多的比較和交換操作嗎？
4. 如何實現在Heap Sort中對數據進行升序或降序排序？
5. 在什麼情況下Heap Sort比其他排序算法更有效率？

說明知識

Heap Sort是一種基於二元樹（Binary Tree）的排序演算法，具體來說就是基於完全二元樹（Complete Binary Tree）來實現的，且可看成是選擇排序的一種改進版本。

在Heap Sort中，先建立一個「最大堆（Max Heap）」或「最小堆（Min Heap）」，然後將堆頂元素與堆底元素互換，接著維護堆的性質，再對剩下的元素進行堆排序，重複上述步驟直到所有元素都排好序。在最大堆的情況下，堆頂元素為最大值，堆底元素為最小值；在最小堆的情況下，堆頂元素為最小值，堆底元素為最大值。

舉例來說，對一個數列{3, 1, 4, 1, 5, 9, 2, 6, 5, 3}進行Heap Sort，具體步驟如下：

1. 建立最大堆

將數列轉化成最大堆並維護其性質：

                        3
                     /     \
                    1       4
                  /  \     /  \
                 1    5   9    2
                / \
               6   5

2. 交換堆頂元素與堆底元素

將堆頂元素3與堆底元素3互換：

                        3
                     /     \
                    1       4
                  /  \     /  \
                 1    5   9    2
                / \
               6   5
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        3
                     /     \
                    1       4
                  /  \     /  \
                 1    5   9    2
                / \
               6   5
                        ↑
                        3

3. 維護堆的性質

因為堆頂元素發生了變化，所以需要重新維護堆的性質：

                        1
                     /     \
                    1       4
                  /  \     /  \
                 3    5   9    2
                / \
               6   5

4. 依次重複步驟2、3

重複步驟2和3，直到所有元素都排好序：

                        1
                     /     \
                    1       2
                  /  \     /  \
                 3    5   9    4
                / \
               6   5
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    1       2
                  /  \     /  \
                 5    5   9    4
                / \
               6   3
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    3       2
                  /  \     /  \
                 5    5   9    4
                / \
               6   1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        2
                     /     \
                    3       1
                  /  \     /  \
                 5    5   9    4
                / \
               6   1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    3       1
                  /  \     /  \
                 5    5   9    4
                / \
               6   2
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    3       1
                  /  \     /  \
                 5    5   4    9
                / \
               6   2
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    3       2
                  /  \     /  \
                 5    5   4    9
                / \
               6   1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        2
                     /     \
                    3       1
                  /  \     /  \
                 5    5   4    9
                / \
               6   1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    3       1
                  /  \     /  \
                 5    5   4    6
                        \
                         9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    3       1
                  /  \     /  \
                 5    5   4    2
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    2       1
                  /  \     /  \
                 5    5   4    3
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    1       2
                  /  \     /  \
                 5    5   4    3
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    1       3
                  /  \     /  \
                 5    5   4    2
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        2
                     /     \
                    1       3
                  /  \     /  \
                 5    5   4    1
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    1       3
                  /  \     /  \
                 5    5   4    2
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    1       2
                  /  \     /  \
                 5    5   4    3
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    1       2
                  /  \     /  \
                 5    4   5    3
                        \
                         6
                          \
                           9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
                        1
                     /     \
                    1       2
                  /  \     /  \
                 4    3   5    5
                        \
                         6
                          \
                           9

最終得到一個排好序的數列：{1, 1, 2, 3, 4, 5, 5, 6, 9}。

優點是平均與最壞情況下，時間複雜度均為O(nlogn)，且適用於大資料排序。但因為常數因素較大，相對於快速排序、合併排序等排序方法，速度相對較慢。

彙總重點

1. 建立堆積：將待排序數列構建成堆積，需要用到「節點下標」和「節點父/子關係」兩個概念，使用最大堆(或最小堆)。

2. 對堆積進行排序：依次取出堆頂元素（最大元素），將其與堆尾元素進行交換，交換後把堆的大小減1，然後對堆頂元素從根節點做節點下潛與節點交換的操作，從而恢復最大堆（或最小堆）特性。

3. 不斷重複上述步驟，直到堆積的大小為1。

知識測驗

1. 實作Heap Sort的函數，將一個陣列從小到大排序。
   範例輸入：[7, 5, 1, 8, 3]
   範例輸出：[1, 3, 5, 7, 8]

2. 如何將Heap Sort的執行時間降至O(nlogn)?
   答案：使用heapify函數來建立heap，此函數的時間複雜度為O(n)。

3. 請解釋Heap Sort不穩定的排序特性。
   答案：當兩個元素的值相等時，排序後它們的相對位置可能會改變。

4. 請列出執行Heap Sort時使用的空間複雜度。
   答案：Heap Sort的空間複雜度為O(1)，因為排序是直接在原始陣列上進行的。

5. 請解釋Heap Sort與Merge Sort的差異。
   答案：Heap Sort使用heap來實現排序，時間複雜度為O(nlogn)，空間複雜度為O(1)。Merge Sort使用分治法來實現排序，時間複雜度為O(nlogn)，空間複雜度為O(n)。