Heap Sort

Methodology

It's use Heap Tree data structure Usually implement by 1-D Array

1. First build a max or min heap
2. Then pop up the node for n-1 times

Time Complexity

Average

O(n log n)

buildMaxHeap(): O(n) execute n-1 times deleteMax: (n-1) x O(log n) = O(n log n)

Worst Case

The same

Space Complexity

Auxiliary Space

O()

Algorithm

Given parent i, left child: (2i+1) right child: (2i+2)

public void HeapSort(int[] data) {
    //初始化，i從最後一個父節點開始調整
    for (int i = len/2-1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F