《iOS面试题整理》- 堆排序

@interface Heap : NSObject

@property (nonatomic, strong, readonly) NSMutableArray *datas;  // 从1开始存数据
@property (nonatomic, assign, readonly) NSInteger maxCount;        // 堆可以存储的最大数据个数
@property (nonatomic, assign, readonly) NSInteger currentCount;     //   当前堆中的元素个数


- (void)setup:(NSInteger)capacity;  // 初始化堆的个数

- (void)insert:(NSInteger)data;

- (void)removeMax; //删除对顶元素

- (void)buildHeap:(NSArray *)datas;  // 根据数组键堆

- (void)sort:(NSArray *)datas;     // 排序
@end

  #import "Heap.h"

@interface Heap ()
@property (nonatomic, strong, readwrite) NSMutableArray *datas;
@property (nonatomic, assign, readwrite) NSInteger maxCount;        // 堆可以存储的最大数据个数
@property (nonatomic, assign, readwrite) NSInteger currentCount;     //   当前堆中的元素个数
@end

@implementation Heap

- (void)setup:(NSInteger)capacity {
    _datas = [NSMutableArray arrayWithCapacity:capacity + 1];
    [_datas addObject:@(-1)];
    _maxCount = capacity;
    _currentCount = 0;
}

- (void)insert:(NSInteger)data {
    if (_currentCount >= _maxCount) return;
    _currentCount++;
    _datas[_currentCount] = @(data);
    
    NSInteger i = _currentCount;
    while (i / 2 > 0 && [_datas[i] integerValue]> [_datas[i/2] integerValue]) {
        [_datas exchangeObjectAtIndex:i withObjectAtIndex:i/2];
        i = i / 2;
    }
}

- (void)removeMax {
    if (_currentCount == 0) return;
    NSNumber *last = [_datas lastObject];
    [_datas replaceObjectAtIndex:1 withObject:last];
    [_datas removeLastObject];
    NSLog(@"移除后的堆结果是 %@",_datas);
    _currentCount--;
    [self heapify:_datas size:_currentCount index:1];
}

- (void)heapify:(NSMutableArray *)datas size:(NSInteger)n index:(NSInteger)i{
    while (YES) {
        NSInteger maxPos = i;
        if (i * 2 <= n && [datas[i] integerValue] < [datas[i * 2] integerValue])  maxPos = i * 2;
        if (i * 2 + 1 <=n && [datas[maxPos] integerValue] < [datas[i * 2 + 1] integerValue]) maxPos = i * 2 + 1;
        if (maxPos == i) break;
        NSLog(@"%ld,%ld", i , maxPos);
        [datas exchangeObjectAtIndex:i withObjectAtIndex:maxPos];
        i = maxPos;
        
        NSLog(@"堆化后的数据是 %@", datas);
    }
}

- (void)buildHeap:(NSArray *)datas {
    NSMutableArray *arrays = [NSMutableArray arrayWithCapacity:datas.count + 1];
    [arrays addObject:@(-1)];
    [arrays addObjectsFromArray:datas];
    
    NSInteger size = datas.count;
    
    for (NSInteger i = size / 2; i >= 1; i--) {
        NSLog(@"------- %ld 次",i);
        [self heapify:arrays size:size index:i];
    }
    
    _datas = arrays;
    _maxCount = datas.count;
    _currentCount = datas.count;
}

- (void)sort:(NSArray *)datas {
    [self buildHeap:datas];
    NSInteger k = datas.count;
    while (k > 1) {
        [_datas exchangeObjectAtIndex:1 withObjectAtIndex:k];
        k--;
        [self heapify:_datas size:k index:1];
    }
}
@end