【基本思想】
将待排序序列构造成一个大根堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值，然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。
堆：具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
此时，我们就将一个无需序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
【算法复杂度】
| 时间复杂度（平均） | 时间复杂度 （最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| O(nlgn) | O(nlgn) | O(nlgn) | O(1) | 不稳定 |
时间复杂度>>>
堆排序的时间，主要是消耗在构建堆和在重建堆时的反复筛选上。
在构建堆的过程，因为我们是从完全二叉树最下层的非叶子结点开始构建的，将它与其孩子结点进行比较和有必要的互换，对于每个非叶子结点来说，其实最多2次比较和互换，故初始化堆的时间复杂度为O(n)。
在正式排序的时候，第i次取堆顶记录和重建堆需要O(logi)的时间（完全二叉树的某个结点到根结点的距离为logi+1），并且需要取n-1次堆顶记录，因此重建堆的时间复杂度为O(nlogn)。所以总的来说，堆排序的时间复杂度为O(nlogn)。
算法稳定性>>>
它是不稳定的排序方法
【动图演示】
【算法实现】
/* ** 堆排序的C++实现 ** 假设：对N个整数进行升序排序 ** HeapAdjust()函数用于调整大根堆 ** 变量index为要调的整的父节点下标 ** 变量j为要调整的子节点下标 */ void HeapAdjust(vector<int>&seq, int index, int len){ seq[0] = seq[index]; // 将要调整的结点的值存储到临时结点中 for(int j = 2 * index; j <= len; j *= 2){ // 循环的调整父节点与子节点的位置关系，使堆满足定义 if(j < len && seq[j] < seq[j + 1]) ++j; // 选择子节点中较大的那一个 if(seq[0] >= seq[j]) break; // 当父节点大于等于两个子节点时，跳出 seq[index] = seq[j]; index = j; } seq[index] = seq[0]; // 将要移动的结点放到正确的位置 } void HeapSort(vector<int>& seq){ int i,length = seq.size(); seq.insert(seq.begin(),0); // 在序列最前面创建一个结点用来存储临时值 for(i = length/2; i>0; i--) // 选择最后一个非叶结点，构造大根堆 HeapAdjust(seq, i, length); for(i = length; i>1; i--){ // 将根结点与无序序列的最后一个结点交换，并调整大根堆，重复这个步骤 seq[1] ^= seq[i]; seq[i] ^= seq[1]; seq[1] ^= seq[i]; HeapAdjust(seq, 1, i-1); } seq.erase(seq.begin()); // 删除临时结点 }