Swift之堆排序

树

在介绍对排序之前，先介绍“树”的相关概念！
树：指不包含回路的连通无向图。有以下一些特性：

• 一棵树中的任意两个节点有且仅有唯一的一条路径连通；
• 一棵树如果有n个节点，那么它一定恰好有n-1条边；
• 在一棵树中加一条边将会构成一个回路。

二叉树

二叉树是一种特使的树，二叉树的特点是每个节点最多只有两个子节点，左边的叫做左子树，右边的叫做右儿树。二叉树中还有两种特殊的树，满二叉树和完全二叉树，满二叉树是指二叉树中每个内部节点都有两个字节点（严格定义是一颗深度为h且有2的h次方-1个节点的二叉树）；完成二叉树是指除了最右边位置上有一个或者几个叶节点缺少外，其他都是丰满（严格定义是：若二叉树的高度为h，除第h层外，其他各层（1~h-1)的节点数都达到最大个数，第h层从右向左连续缺若干节点）

堆

堆是一种特使的完全二叉树，堆分为两种。一种是所有父节点都要比子节点大，这称为最大堆；另一种是素有的父节点比所有的子节点都要小，这称为最小堆。如下图所示，是一个最小堆。

最小堆.png

堆排序

堆的特性非常适合来用来做排序算法。下面介绍一种利用堆来排序的算法：

• 根据要排序的数组，建立一个最大堆：把n个元素建立一个堆，可以将n个节点自顶向下，从左到右的方式编码，这样就可以把n个节点转换成一个完全二叉树。紧接着从最后一个非叶节点开始到根节点，逐个扫描所有的节点，根据需要将当前的节点向下调整，直到以当前节点为根节点的子树符合最大堆得特性。
• 堆排序：建立了最大对以后，最大的元素就是堆的顶点h[1],我们将h[1]和h[n]交换，此时h[n]就是数组中最大的元素，交换以后将h[1]向下调整以保持最大堆得特性。这样，最大的元素已经归位，然后将堆得大小减一，然后重复上面的步骤，知道堆得大小变成1为止。

完整代码如下：

<pre>
var tempList:[Int] = [99,5,36,7,22,17,46,12,2,19,25,28,1,92]

//交换数组内的元素
func swapInTemp(x:Int,y:Int) {
let t:Int = tempList[x]
tempList[x] = tempList[y]
tempList[y] = t
}

//向下调整
func siftDown(i:Int,count:Int) {

var flag = 0
var temp = 0
var tempI = i

while (flag == 0) && (tempI*2 < (count - 1)) {
    
    if tempList[tempI] < tempList[tempI*2 + 1] { //小于左子树
        temp = tempI*2 + 1
    } else {
        temp = tempI
    }
    
    if (tempI*2 + 2) <= (count - 1) { //如果有右子树
        if tempList[temp] < tempList[tempI*2 + 2] {
            temp = tempI*2 + 2
        }
    }
    
    if temp != tempI {
        swapInTemp(x: temp, y: tempI)
        tempI = temp
    }
    else{
        flag = 1
    }
}

}

//创建最大堆
func creatheap(list: inout [Int]) {

var i = list.count / 2 - 1

while i >= 0 {
    siftDown(i: i, count: list.count)
    i-=1
}

}

//堆排序(从小到大)
func heapSort(list: inout [Int]) {

var max = list.index(before: list.endIndex)
while max > 0 {
    swapInTemp(x: 0, y: max)
    siftDown(i: 0, count: max)
    max-=1
}

}

creatheap(list: &tempList)
heapSort(list: &tempList)
print(tempList)//[1, 2, 5, 7, 12, 17, 19, 22, 25, 28, 36, 46, 92, 99]
</pre>