#include <iostream>
using namespace std;

void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}

void printArray(int arr[],int length){
    for(int i = 0;i < length;i++)
        cout << arr[i] << " ";
    cout << endl;
}
//某个数处于index上，继续往上移动
void heapInsert(int arr[],int index){
    while(arr[index] > arr[(index-1)/2]){//如果index节点大于他的父节点，那么交换位置
        swap(arr[index],arr[(index-1)/2]);
        index = ((index-1) >> 1);
    }
}
//某个数处在index上，能否往下移动
void heapfiy(int arr[],int index ,int heapSize){
    int left = index * 2 + 1;//左孩子
    while(left < heapSize){//下方还有孩子的时候
        //右孩子存在，两个孩子谁最大把下标给largest
        int largest = (left + 1 < heapSize) && (arr[left + 1] > arr[left]) ? left + 1 : left;
        //父和较大的孩子直接比较，谁的大把下标给largest
        largest = arr[largest] > arr[index] ? largest:index;
        if(largest == index){
            break;
        }
        swap(arr[largest],arr[index]);
        index = largest;
        left = index * 2 + 1;
    }
}

void heapSort(int arr[],int length){
    if(arr == NULL || length < 2){
        return;
    }

    for(int i = 0;i < length;i++){//O(N)
        heapInsert(arr,i);//O(logN)
    }
    int heapSize = length;
    swap(arr[0],arr[--heapSize]);
    while(heapSize > 0){//O(N)
        heapfiy(arr,0,heapSize);//O(N)
        swap(arr[0],arr[--heapSize]);
    }
}


int main(){
    int arr[] = {12,6,89,663,2,4,3,5,7,9,222,5,78,999,44};
    int length = sizeof(arr)/sizeof(arr[0]);

    printArray(arr,length);
    heapSort(arr,length);
    printArray(arr,length);
        
    return 0;
}