3.3.3 - Heap Sort

1. 演算法

將{5, 3, 2, 1, 7, 8, 9, 10}

1. 將資料以Bottom-Up方式建立Max-Heap

2. 執行Delete-Max

   1. SWAP(Root, the last node)

   2. 刪除最大值

   3. 將剩下的Heap調整為Max-Heap

output=10

output=9

void HeapSort(char *heap){
    int n = strlen(heap);
    //build heap
    for (int i = n/2-1; i>=0; i--)  //i從最後一個父點開始
        AdjustBottomUp(heap, i, n-1);
    //delete max
    for (int i = n-1;i>0;i--){
        Swap(&heap[0], &heap[i]); //將max移到最後
        for (int j = i/2-1; j>=0; j--)
            AdjustBottomUp(heap, j, i-1);
    }
}

2. 性質

• Time Complexity: $O(nlogn)$

  1. 以Bottom-Up建立Heap共花$O(n)$

  2. 執行Delete-Max，每一回合共花 $O(logn)$，共有n回合

• Space Complexity: $O(1)$

Heap sorting is a unstable sorting method.