小序：什么是堆？
先了解一下什么是堆，堆是计算机科学中的一种特别的树状数据结构,堆总是一棵完全二叉树,它总是满足下列性质:
性质1：堆中某个节点的值总是不大于或不小于其父节点的值;
性质2：堆总是一棵完全二叉树。
堆的特征就是:给定堆中任意节点P和C,若P是C的母节点,那么P的值会小于等于(或大于等于) C 的值”。将根节点最大的堆叫做最大堆、大顶堆或大根堆，根节点最小的堆叫做最小堆、小顶堆或小根堆，如下图：。常见的堆有二叉堆、斐波那契堆等。
同时，我们对以上堆的这种逻辑结构映射到数组中就是下面这个样子：
我们用简单的公式定义一下大顶堆和小顶堆：
大顶堆：a[I] >= a[2i+1] && a[I] >= a[2i+2]
小顶堆：a[I] <= a[2i+1] && a[I] <= a[2i+2]
堆排序的思路？
首先我们先将数组序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
堆排序
基于上面对堆的了解，相信你对堆排序会有了更好的认识。堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
1. 算法步骤
创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
2. 动图演示
3. 代码实现
/// 堆排序法
/// [微信公众号：疯狂1024]
/// - Parameter array:传入参数的数组
/// - Returns: 返回排序后的数组
publicfuncheapSort(_array: [Int]) -> [Int] {
guard!array.isEmptyelse{return[] } // 非空判断，避免崩溃
varpreArray:Array = array // 对 arr 进行拷贝，不改变参数内容
buildMaxHeap(&preArray) // 建立大顶堆（堆化处理）
foriin(0..<preArray.count).reversed() {
preArray.swapAt(i,0) // 找到最大堆顶后将堆顶的数值和第i个进行互换
heapify(&preArray, nodeIndex:0, len: i) // 堆化处理(互换堆顶数值后结构发生变化，需要再次堆顶化处理)
}
returnpreArray
}
///建立大顶堆
/// - Parameter array: 传入参数的数组，注意是传址不是传值
privatefuncbuildMaxHeap(_array:inout[Int]) {
letminNodeIndex =Int(floor(Double(array.count/2))-1) // 寻找“最小的”节点位置,即中间平分后带子叶的节点
forindexin(0...minNodeIndex).reversed() { // 循环所有节点
heapify(&array, nodeIndex: index, len: array.count)
}
}
/// （大顶）堆化调整
/// - Parameters:
/// - array: 传入参数的数组，注意是传址不是传值
/// - nodeIndext: 节点位置
/// - len: 想要要堆化的数组长度
privatefuncheapify(_array:inout[Int], nodeIndex:Int, len:Int) {
letleft =2*nodeIndex+1
letright =2*nodeIndex+2
varlargest = nodeIndex
// 寻找最大数值位置
ifleft<len&&array[left]>array[largest] {
largest = left
}
ifright<len&&array[right]>array[largest] {
largest = right
}
iflargest!=nodeIndex {
array.swapAt(nodeIndex, largest) // 互换数值，把最大数值放到节点位置
heapify(&array, nodeIndex: largest, len: len) // 互换后数据结构发生变化，继续进行堆化处理
}
}
