Fork me on GitHub

堆排序(oc代码实现)

发表于 | 分类于

概念

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

分类

  • 小根堆

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

  • 大根堆

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

举例

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

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

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

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

318837-20160422104522335-1248911478.png

如上图所示，序列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]
318837-20160422104522991-406805984.png

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

具体代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//  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<length) {//这里的操作是先比较左右子节点的大小，那其中最大的再去跟父节点比较
        if (array[rightChild]<array[rightChild-1]) {
            maxChild =[array[rightChild-1] intValue];
            maxChildIndex = rightChild-1;
        }else{
            maxChild =[array[rightChild] intValue];
            maxChildIndex = rightChild;
        }
    }else if (rightChild-1<length){
        maxChild = [array[rightChild-1] intValue];
        maxChildIndex = rightChild-1;
    }
    if (maxChild>0) {
        if ([array[parent] intValue]<maxChild) {
            [array replaceObjectAtIndex:parent withObject:@(maxChild)];
            [array replaceObjectAtIndex:maxChildIndex withObject:@(parentValue)];
            [self headpSort:array parent:maxChildIndex length:length];//如果子节点是其他子节点的父节点的话，有可能比其子节点小，故需要递归
        }
    }
}
@end

总结

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

参考

堆排序

0%