最大堆排序

最大堆（Max-Heap）是一種二叉堆，其中每個節點的值都不小於其子節點的值。最大堆排序是一種利用最大堆特性來排序數組的方法。最大堆排序的步驟如下：

1. 構建最大堆：將數組轉換為最大堆。
2. 堆排序：將最大堆的根節點（最大值）與數組的最後一個元素交換，然後調整剩餘的子樹以確保新的子樹仍然是一個最大堆。重複這個過程直到整個數組有序。

下面是一個簡單的最大堆排序的偽代碼實現：

function maxHeapSort(array):
    buildMaxHeap(array)
    for i from length of array downto 1:
        swap array[0] with array[i]
        decrease the size of heap by 1
        maxHeapify(array, 0, i - 1)

function buildMaxHeap(array):
    for i from (length of array) / 2 downto 1:
        maxHeapify(array, i)

function maxHeapify(array, i, heapSize):
    largest = i
    left = 2*i + 1
    right = 2*i + 2
    if left <= heapSize and array[left] > array[largest]:
        largest = left
    if right <= heapSize and array[right] > array[largest]:
        largest = right
    if largest != i:
        swap array[i] with array[largest]
        maxHeapify(array, largest, heapSize)

這個算法的時間複雜度是O(n log n)，其中n是數組的元素個數。空間複雜度也是O(n log n)，因為我們需要額外的空間來存儲堆結構。