β

堆排序(OC代码实现)

Harries Blog™ 56 阅读

概念

堆是一棵顺序存储的完全二叉树,分为大根堆和小根堆

分类

每个结点的关键字都不大于其孩子结点的关键字。

每个结点的关键字都不小于其孩子结点的关键字

举例

举例来说,对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时,称之为堆:

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整;

堆排序(OC代码实现)

如上图所示,序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个父结点,元素3和元素8。

元素3在数组中以R[0]表示,它的左孩子结点是R[1],右孩子结点是R[2]。

元素8在数组中以R[1]表示,它的左孩子结点是R[3],右孩子结点是R[4],它的父结点是R[0]。可以看出,它们满足以下规律:

总结

设当前元素在数组中以R[i]表示,那么,

(1) 它的左孩子结点是:R[2*i+1];

(2) 它的右孩子结点是:R[2*i+2];

(3) 它的父结点是:R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

OC 代码 实现

思路

1. 根据初始数组去构造初始堆(构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大)。

2. 每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。

其实思路很简单,最重要的是怎么将一个初始化的数组构建一个大根堆呢??

采用的方式是自下而上,从右到左自下而上,从右到左的思路,以3个为一个单元,进行构建。

这么说大家可能还会搞不懂,接下来让我们举例说明!

假设有一个无序数组[1, 3, 4, 5, 2, 6, 9, 7, 8, 0]

堆排序(OC代码实现)

这其中有个很重要的操作就是递归操作,图中的(4)

具体代码

代码中我加了很多 注释 ,相信大家能够看懂。:-D

//  ViewController.m
//  Copyright ? 2017年 FlyOceanFish. All rights reserved.
//
#import "ViewController.h"
@interface ViewController ()
{
    NSMutableArray *array;
}
@end
@implementation ViewController
- (void)viewDidLoad {
    [super viewDidLoad];
    array = [@[@20,@1,@4,@3,@40,@22,@9,@35,@6,@11,@18,@0] mutableCopy];
    for (NSInteger i=array.count/2; i>=0; i--) {
        [self headpSort:array parent:i length:array.count];//初始化建立大根堆
    }
    for (NSInteger i=array.count-1; i>0; i--) {//循环交换将最大的R0放到最后边
        NSInteger tem = [array[0] integerValue];
        [array replaceObjectAtIndex:0 withObject:@([array[i] integerValue])];
        [array replaceObjectAtIndex:i withObject:@(tem)];
        [self headpSort:array parent:0 length:i];//交换完成后,树中最大的自然排到了最后边,故只要对剩余的i个数重新调整为大根堆
        NSLog(@"排序后:%@",array);
    }
}
/**
 这种遍历比较是自下而上的进行比较方式(从树的下部往上比较,以三个数为一个部分(假设左右子节点都有))
 */
- (void)headpSort:(NSMutableArray *)array parent:(NSInteger)parent length:(NSInteger)length{
    NSInteger parentValue = [array[parent] intValue];
    NSInteger rightChild = 2*parent+2;
    NSInteger maxChildIndex = -1;
    NSInteger maxChild = -1;
    if (rightChild

总结

看的过程可能很爽,一看就明白,也有可能 里雾里。实践出真知!所以建议大家用代码根据原理亲自去实现一遍,相信一切皆明了。

参考

堆排序

PS:如果您想和业内技术大牛交流的话,请加qq群(527933790)或者关注微信公众 号(AskHarries),谢谢!

转载请注明原文出处: Harries Blog™ » 堆排序(OC代码实现)

作者:Harries Blog™
追心中的海,逐世界的梦
原文地址:堆排序(OC代码实现), 感谢原作者分享。

发表评论