# Heap Sort
###### tags: `排序法`

### 概念
* **build** a heap by an unsorted array
* turn heap to **max heap**
1. swap root and arr[last]
2. **heapify(arr[last])**
3. loop step 2 until index=0
4. then you have a sorted array ascending

### algorithm

Heapsort(int[] arr, int n){
    //create a max heap
    for(int i=n/2-1; i>=0; i--){
        //檢查每個不是葉點的節點是否為max heap，index = n/2後就都是葉點
        heapify(arr,n,i);
    }
    
    //swap first and last node
    //heapify(root)
    //create max heap on reduced array
    for(int i=n-1; i>=0; i--){
        swap(arr[0],arr[i]);
        heapify(arr,i,0);
    }
}

Heapify(arr,int i){
    int left = 2*i+1;
    int right = 2*i+2;
    
    if(left<n && arr[left]>arr[i]){
        max = left;
    }
    
    if(right<n && a[right]>arr[max]){
        max = right;
    }
    
    if(max!=i){
        swap(arr[i],arr[max]);
        Heapify(arr,n,max);
    }
}

### 時間複雜度
* build max heap = **O(n)**
* heapify = **O(logn)**
* 綜合上述：best/worst/average case = **O(nlogn)**
* 需要額外空間 O(1)，屬於unstable排序

---
資料來源：GeeksforGeeks [website](https://www.geeksforgeeks.org/heap-sort/) and [youtube channel](https://www.youtube.com/watch?v=MtQL_ll5KhQ)
相關文章：[Heap](https://hackmd.io/p9YTHxyVSjuhEqiHLE2vRA?view)