堆排序

顾名思义，是利用堆这种数据结构来进行排序的算法。

如果你了解堆这种数据结构，你应该知道堆是一种优先队列，两种实现，最大堆和最小堆，由于我们这里排序按升序排，所以就直接以最大堆来说吧。

我们完全可以把堆（以下全都默认为最大堆）看成一棵完全二叉树，但是位于堆顶的元素总是整棵树的最大值，每个子节点的值都比父节点小，由于堆要时刻保持这样的规则特性，所以一旦堆里面的数据发生变化，我们必须对堆重新进行一次构建。

既然堆顶元素永远都是整棵树中的最大值，那么我们将数据构建成堆后，只需要从堆顶取元素不就好了吗？ 第一次取的元素，是否取的就是最大值？取完后把堆重新构建一下，然后再取堆顶的元素，是否取的就是第二大的值？ 反复的取，取出来的数据也就是有序的数据。

我们以[ 8，2，5，9，7，3 ]这组数据来演示。

首先，将数组构建成堆。

既然构建成堆结构了，那么接下来，我们取出堆顶的数据，也就是数组第一个数 9 ，取法是将数组的第一位和最后一位调换，然后将数组的待排序范围 -1。

现在的待排序数据是[ 3，8，5，2，7 ]，我们继续将待排序数据构建成堆。

取出堆顶数据，这次就是第一位和倒数第二位交换了，因为待排序的边界已经减 1 。

继续构建堆

从堆顶取出来的数据最终形成一个有序列表，重复的步骤就不再赘述了，我们来看一下代码实现。

代码实现

void sort(vector<int>& arr)
{
    int length = arr.size();
    buildHeap(arr, length);
}

void buildHeap(vector<int>& arr, int length)
{
    for(int i = length/2; i >=0; i--) {
        sink(arr, i, length);
    }
}

// 下沉调整
void sink(vector<int>& arr,int index, int length)
{
    int leftChild = 2 * index +1; // 左孩子下标
    int rightChild = 2 * index + 2; // 右孩子下标
    int present = index;    // 要调整的节点下标

    // 下沉左边
    if(leftChild < length && arr[leftChild] > arr[present]) {
        present = leftChild;
    }

    // 下沉右边
    if(rightChild < length && arr[rightChild] > arr[present]) {
        present = rightChild;
    }

    // 如果下标不想等 证明调换过了
    if (present != index)
    {
        // 交换值
        int temp = arr[index];
        arr[index] = arr[present];
        arr[present] = temp;

        // 继续下沉
        sink(arr, present, length);
    }

}