堆排序

概念

堆是按照一定规则顺序存储的完全二叉树(二叉树是每个节点最多有两个子树的树结构)，其中可以分为大根堆和小根堆。

• 大根堆: 每个父结点的关键字都大于其子节点的关键字(如果有子结点的话)
• 小根堆: 每个父结点的关键字都小于其子节点的关键字(如果有子结点的话)

举例来说，有个数组[A0, A1, A2, A3...An]假设父结点为Ai(其中i=1,2,…,n/2向下取整), 由二叉树的排列规律可知其左子结点为A(2 * i + 1), 右子结点为A(2 * i + 2)因此大根堆必须满足:Ai >= A(2 * i + 1)且Ai >= A(2 * i + 2), 小根堆必须满足Ai <= A(2 * i + 1)且Ai <= A(2 * i + 2)

假如有个数列[3, 8, 15, 31, 25]，以二叉树的形式表示如下图：

318837-20160422104522335-1248911478.png

首先需要按照堆的规则去构造初始堆(即构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大)，构造规则为不同行从下往上、相同行从右往左分别比较每一个子二叉树的结点，如果父结点的关键字不是最大值，让子节点中最大的值与父节点进行交换。如此遍历一遍后可以得到一个初始堆。
注意: 当第一级二叉树子结点值大于父结点的值进行交换后，交换后新的子结点作为父结点的第二级子二叉树中如果依然不是最大值则需要再次与其最大子结点进行交换。例:有个数组[5,3,1,8,7]在调整后变为[5,8,1,3,7]->[8,5,1,3,7]，然而此时由于在(5,3,7)这个子二叉树中父结点5不是最大值，因此需要再次向下比较一次进行交换

在初始堆的基础上交换数组中被调整的首尾元素，并让数组重新调整为大根堆(这次调整忽略移到末尾的元素),采用递归的方式就可以依次把所有元素按升序排列到数组中了。

OC语言实例

给可变数组创建一个分类来存放该堆排序方法。

- (NSMutableArray *)heapSort
{
    // 判断是不是NSNumber的数组
    BOOL isFullNSNumber = YES;
    for (id value in self) {
        if (![value isKindOfClass:[NSNumber class]]) {
            isFullNSNumber = NO;
        }
    }
    
    NSAssert(isFullNSNumber, @"数组中应当全是NSNumber对象");
    
    // 初始化一个终止计算结点索引位置(一次排序后把最大值移动到数组计算结点范围的末尾)
    int endIndex = (int)(self.count - 1);
    while (endIndex > 0) {
        // 遍历一次数组按照堆的规则排序一次
        [self binaryTreeSortWithArray:self maxIndex:endIndex];
        // 将建立堆得到的最大根与数组中最后一个数组互换
        [self exchangeObjectAtIndex:0 withObjectAtIndex:endIndex--];
    }
    
    return self;
}

/// 二叉树规则(大根堆)排序 -- (排序范围为索引为0的位置到待排序结点最大索引位置)
- (void)binaryTreeSortWithArray:(NSMutableArray *)array maxIndex:(int)maxIndex
{
    // 从可排序结点的最大索引处开始进行排序
    for (int i = maxIndex; i >= 0; i--) {
        // 获取移动后的子结点的索引
        int newIndex = [self compareNodesSizeWithMaxIndex:maxIndex fatherNodeIndex:i];
        while (newIndex > 0) {
            newIndex = [self compareNodesSizeWithMaxIndex:maxIndex fatherNodeIndex:newIndex];
        }
    }
}

/// 递归比较指定索引位置的结点与其左右子节点的大小
- (int)compareNodesSizeWithMaxIndex:(int)maxIndex fatherNodeIndex:(int)fatherIndex
{
    // 获取当前索引位置的左右子节点索引
    int leftIndex = fatherIndex * 2 + 1;
    int rightIndex = fatherIndex * 2 + 2;
    
    // 该索引和左右子节点值
    NSNumber *currentValue = [self objectAtIndex:fatherIndex];
    NSNumber *leftValue = nil;
    NSNumber *rightValue = nil;
    if (leftIndex <= maxIndex) {
        leftValue = [self objectAtIndex:leftIndex];
    }
    if (rightIndex <= maxIndex) {
        rightValue = [self objectAtIndex:rightIndex];
    }
    
    if (rightValue != nil) // 右子节点存在, 则左子节点必定存在, 判断三者的值并把最大值换到父节点上
    {
        if (currentValue.doubleValue > leftValue.doubleValue && currentValue.doubleValue > rightValue.doubleValue) {
            return -1;
        }else {
            // 与父节点进行交换的结点的索引
            int index = (leftValue.doubleValue > rightValue.doubleValue ? leftIndex : rightIndex);
            [self exchangeObjectAtIndex:fatherIndex withObjectAtIndex: index];
            // 移动完毕之后同时还要进行(被移动到子节点的值)与(该被移动节点的左右子节点值)进行比较 -- 递归
            return index;
        }
    }
    else if (leftValue != nil) // 右结点不存在, 左结点存在, 判断左结点是否大于父结点的值
    {
        if (currentValue.doubleValue < leftValue.doubleValue) {
            [self exchangeObjectAtIndex:fatherIndex withObjectAtIndex:leftIndex];
            return leftIndex;
        }else {
            return -1;
        }
    }
    
    return -1;
}