【基本思想】

堆排序利用了堆这一数据结构来进行排序，其基本思想是：将待排序的记录构成堆，然后不断将堆顶元素移走，并将剩余的记录调整成堆，直到堆空

对于大根堆来说，其堆排序结果为降序序列，对于小根堆来说，其堆排序结果为升序序列

堆排序主要需要解决两个操作：

1）根据初始数组去构造初始堆，构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大/小

2）每次输出堆顶元素，并将堆顶元素和堆尾元素交换，把剩下元素重新调整为堆

堆排序的宏观排序过程如下图

【堆的建立】

无论是大顶堆还是小顶堆，在建立堆时，首先根据序列取构建一个完全二叉树，之后从最后一个节点起，不断交换元素，以保证所有的父结点都比它的孩子结点数值大/小

以序列 $\{1, 3, 4, 5, 2, 6, 9, 7,8,0\}$ 建立大顶堆过程为例：

【堆的调整】

在建立堆后，进行堆排序，每次将堆顶元素输出，并将堆顶元素与堆尾元素互换，之后删除堆尾元素，此时不满足堆的性质，需要进行调整

以序列 $\{1, 3, 4, 5, 2, 6, 9, 7,8,0\}$ 利用大顶堆进行堆排序的过程为例：

【性能分析】

堆排序适用于顺序存储、链式存储结构，在进行堆的调整时，可能会将后面的相同关键字的元素调整到前面，因此其是一种不稳定排序算法

堆排序仅需常数个辅助空间，作为待插入记录的暂存单元，因此其空间复杂度为：

$O(1)$

对于堆排序来说，其建堆的时间复杂度为 $O(n)$，之后有 $n-1$ 次向下调整操作，每次调整的时间复杂度为 $O(h)$，因此时间复杂度为：

$O(nlog_2n)$

【实现】

以大根堆为例

1）堆的建立

对于 $n$ 个结点的完全二叉树，最后一个结点是第 $\left \lfloor \frac{n}{2}\rfloor \right.$ 个结点的孩子

因此，建立堆时，仅需要调整第 $\left \lfloor \frac{n}{2}\rfloor \right.$ 个结点为根的子树，之后依次向前对 $\left \lfloor \frac{n}{2}\rfloor \right.-1$ ~ $1$ 为根的结点进行调整

void buildMaxHeap (int a[], int n) {
    for (int i = n/2; i > 0; i--) //调整a[2/n]到a[1]
        adjustHeap (a, i, n);
}

2）堆调整

void adjustHeap (int a[], int k, int n) { //调整以k为根的子树
    int temp = a[k]; //暂存a[k]
    for (int i = 2*k; i <= n; i = i*2) { 
        if (i < n && a[i] < a[i+1]) //取关键字较大子结点的下标
            i++;
        if(temp >= a[i])
            break;
        else {
            a[k] = a[i]; //将a[i]调整到双亲结点上
            k = i; //修改k值，以继续向下筛选
        }
    }
    a[k] = temp; //被筛选结点放入最终位置
}

3）堆排序

void heapSort (int a[], int n) {
    buildMaxHeap(a, n);
    for (int i=n; i>1; i--) {
        swap (a[i], a[1]); //输出堆顶元素，并与堆底元素互换
        adjustHeap(a, 1, i-1); //调整剩余i-1个元素
    }
}