原理

利用完全二叉树的性质，构建堆积树，快速查找到目标元素

基本思想：把待排序的元素按照大小在二叉树位置上排列，排序好的元素要满足：父节点的元素要大于等于其子节点；这个过程叫做堆化过程，如果根节点存放的是最大的数，则叫做大根堆；如果是最小的数，自然就叫做小根堆了。根据这个特性（大根堆根最大，小根堆根最小），就可以把根节点拿出来，然后再堆化下，再把根节点拿出来……循环到最后一个节点，就排序好了。

其实整个排序主要核心就是堆化过程，堆化过程一般是用父节点和他的孩子节点进行比较，取最大的孩子节点和其进行交换；但是要注意这应该是个逆序的，先排序好子树的顺序，然后再一步步往上，到排序根节点上。然后又相反（因为根节点也可能是很小的）的，从根节点往子树上排序。最后才能把所有元素排序好。

代码实现

（大根堆实现升序排列）

vector<int> sortArray(vector<int>& nums) {
    BuildHeap(nums);
    for(int i = nums.size()-1;i>0;i--){
        RebuildHeap(nums,i);
    }
    return nums;
}

//自下而上初始化堆
void BuildHeap(vector<int>& nums) {
    int length = nums.size();
    for(int i = nums.size()/2 - 1;i>=0;i--) {
        _sort(nums,i,length);
    }
}

// 取堆头元素、自上而下重新排序
void RebuildHeap(vector<int>& nums, int length) {
    swap(nums[0],nums[length]);
    _sort(nums,0,length);
}

// 堆排序的辅助函数
void _sort(vector<int>& nums, int node, int length) {
    int cur = node;
    int child = 2*node + 1;
    for(;child<length;) {
        if((child+1)<length&&nums[child+1]>nums[child])
            child ++;

        if(nums[cur]>nums[child])
            break;
        else{
            //如果不符合大小顺序，交换值并让cur指向变更过的child节点
            swap(nums[cur],nums[child]);
            cur = child;
            child = 2*cur + 1;
        }
    }
}