HeapSort.cpp

# include<iostream>
# include<vector>

using namespace std;


void Heaptify(vector<int>& arr,int start,int end){
    int dad=start;
    int son=dad*2+1;
    while(son<=end){
        if(son+1<=end && arr[son]<arr[son+1]){
            son++;
        }
        if(arr[son]<arr[dad]){
            return;
        }else{
            swap(arr[son],arr[dad]);
            dad=son;
            son=dad*2+1; 
        }
    }
}

//时间复杂度 O(nlogn);
void HeapSort(vector<int>& arr,int size){
    for(int i=size/2-1;i>=0;i--){
        Heaptify(arr, i, size-1);
    }
    for(int i=size-1;i>0;i--){
        swap(arr[0],arr[i]);
        Heaptify(arr, 0, i-1);
    }
}


int main(){
    vector<int> arr={1,2,110,2,40,482,93,40,2,20,59,99};
    HeapSort(arr,arr.size());
    for(int i=0;i<arr.size();i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}