二叉堆 demo

二叉堆其实就是一颗完全二叉树，所以又可以叫做完全二叉堆

二叉堆的底层可以用数组来实现

对于二叉堆的索引 i ：

1. 如果 i= 0 ， 那么为根节点
2. 如果 i > 0 ， 那么他的父节点的编号为 floor((i - 1) / 2)
3. 如果 2i + 1 <= n(总节点个数) - 1 ,他的左子节点的编号为 2i + 1
4. 如果 2i+ 1 > n -1 ,他无左子节点
5. 如果 2i+ 2 <= n -1,他的右子节点的编号为 2i + 2
6. 如果2i + 2 > n -1 ，他无右子节点

添加元素

如果是大顶堆，默认先将元素添加到数组的尾部，然后再拿这个元素和自己的父节点作比较，如果自己比父节点大，则交换位置，循环执行此操作，如果当前节点比父节点小，或者没有父节点，则退出循环，这个过程叫做上滤，时间复杂度为logn。

删除元素

1. 将最后一个节点替换根节点
2. 删除最后一个节点
3. 循环执行以下操作，下滤(sift down)，事件复杂度O(logn),
  3.1 如果node<子节点，那么就与最大的子节点交换位置
  3.2 如果node>=子节点或者node没有子节点，退出循环

top k 问题

//top k 问题
// 找到一组数中，最大的前几个
- (void)testFindMax{
    NSArray *arr = @[@1,@2,@3,@4,@5,@6,@7,@8,@9,@10];
    int k =5;
    SCXBinaryHeap *heap = [[SCXBinaryHeap alloc] initWithDelegate:self];;

    // 找到最大的前五个，现将前五个额元素，放入小顶堆中，然后之后的每一个元素，如果比堆顶大，那么就执行replace，这样做的目的其实就是，默认先将前五个作为最大，然后如果发现有大的，就一次替换，因为堆顶是最小的，所以到最后，小顶堆的元素一定是最后要找的,时间复杂度为nlogk，k为要寻找的个数
    // 这里是找到最小的前五个数
    for (int i = 0; i < arr.count; i ++) {
        if (heap.size < k) {
            [heap add:arr[i]];
        } else if ([self compareA:heap.getTopObject valueB:arr[i]]){
            [heap replaceTopObject:arr[i]];
        }
    }
    NSLog(@"%@",heap);
}

代码示例

//
//  SCXBinaryHeap.m
//  TestArithmetic
//
//  Created by 孙承秀 on 2020/6/30.
//  Copyright © 2020 孙承秀. All rights reserved.
//

#import "SCXBinaryHeap.h"
#define DefaultCapacity 10
@interface SCXBinaryHeap()
{
    NSInteger _size;
    NSInteger _capacity;
}
@property(nonatomic,weak)id <SCXBinaryHeapDelegate>delegate;
@property(nonatomic,strong)NSMutableArray *array;
@end
@implementation SCXBinaryHeap
-(instancetype)initWithDelegate:(id<SCXBinaryHeapDelegate>)delegate{
    if (self = [super init]) {
        self.delegate = delegate;
        self.array = [NSMutableArray arrayWithCapacity:DefaultCapacity];
        _capacity = DefaultCapacity;
    }
    return self;
}
- (instancetype)initWithArray:(NSArray *)arr delegate:(id<SCXBinaryHeapDelegate>)delegate{
    if (self = [super init]) {
        self.delegate = delegate;
        if (!arr || arr.count == 0) {
            _array = [NSMutableArray arrayWithCapacity:DefaultCapacity];
            _size = 0;
        } else {
            NSInteger count = arr.count;
            _capacity = count;
            _size = count;
            self.array = arr.mutableCopy;
            [self heapify];
        }
    }
    return self;
}
- (void)heapify{
    // 自下而上下滤
    for (NSInteger i = (_size >> 1) - 1; i >= 0; i --) {
        [self siftDown:i];
    }
}
- (void)add:(nonnull id)object {
    if ([self isNULL:object]) {
        return;
    }
    // 动态扩容
    [self ensureCapcity:_size + 1];
    // 将元素放在最后,然后将当前size+1
    _array[_size++] = object;
    // 将当前最后一个元素上滤
    [self siftUp:_size-1];
}
-(id)removeTopObject{
    if ([self isEmpty]) {
        return nil;
    }
    NSInteger lastIndex = --_size;
    id obj = _array[0];
    _array[0] = _array[lastIndex];
    [_array removeObjectAtIndex:lastIndex];
    [self siftDown:0];
    return obj;
}
- (id)replaceTopObject:(id)object{
    if ([self isNULL:object]) {
        return nil;
    }
    id obj = nil;
    if (_size == 0) {
        _size ++;
        _array[0] = object;
    } else {
        obj = _array[0];
        _array[0] = object;
        [self siftDown:0];
    }
    return obj;
}
-(NSInteger)size{
    return _size;
}
-(BOOL)isEmpty{
    return _size == 0;
}

- (void)clear {
    [_array removeAllObjects];
    _size = 0;
}

- (nonnull id)getTopObject {
    return _array.firstObject;
}

// 上滤
- (void)siftDown:(NSInteger)index{
    //第一个叶子节点的所以就是非叶子节点的数量，因为为完全二叉树，所以，要么没有左右子节点，要么只有左节点，不可能出现只有右子节点的情况
    // index < 第一个叶子节点的索引，这样就能保证他能和有子节点的进行交换
    // 必须保证index 位置为非叶子节点，因为这样可以找到左节点，或者左右节点，进行交换
    // 非叶子节点的数量为 二叉树节点数量除以二
    
    id obj = _array[index];
    // 第一个非叶子节点的索引
    NSInteger half = _size >> 1;
    while (index < half) {
        // 要么只有左子节点
        // 要么右左右子节点
        // 左子节点的索引为 2i +1 ,右子节点的索引为 2i+2
        NSInteger leftIndex = (index << 1) + 1;
        id leftObjf = _array[leftIndex];
        NSInteger rightIndex = leftIndex +1;
        id rightObj = _array[rightIndex];
        
        // 选出最大值
        id maxObj = leftObjf;
        NSInteger maxIndex = leftIndex;
        
        if (rightIndex < _size && [self.delegate compareA:rightObj valueB:leftObjf]) {
            // 右节点比左节点大
            maxObj = rightObj;
            maxIndex = rightIndex;
        }
        
        // 选出左右最大的节点和index之后，和当前节点进行比较
        if ([self.delegate compareA:obj valueB:maxObj]) {
            // 如果当前节点比左右子节点中最大的那一个都打大，就退出不用交换了
            break;
        }
        // 如果当前节点比左右节点中的其中一个小，那么将当前位置，赋值为最大值,将最大值一次上滤，然后自己下沉，记住位置
        _array[index] = maxObj;
        index = maxIndex;
    }
    _array[index] = obj;
}
- (void)siftUp:(NSInteger)index{
    // 取出当前 index 的元素
    id currentValue = _array[index];
    // 循环上滤
    while (index > 0) {
        // 父节点的索引
        NSInteger parentIndex = (index -1) >> 1;
        // 父节点的值
        id parentObj = _array[parentIndex];
        // 比较
        if (![self.delegate compareA:currentValue valueB:parentObj] ) {
            // 如果当前的值比父节点的值小，说明符合大顶堆的要求，直接退出
            break;;
        }
        // 如果当前的值比父节点大，那么交换位置
        _array[index] = parentObj;
        index = parentIndex;
    }
    _array[index] = currentValue;
}
/// 动态扩容
- (void)ensureCapcity:(NSInteger)capcity{
    NSInteger oldCapcity = _capacity;
    if (oldCapcity >= capcity) {
        return;
    }
    NSInteger newCapcity = oldCapcity + (oldCapcity >> 1);
    [self resMemory:newCapcity];
}
- (void)resMemory:(NSInteger)newCapcity{
    NSInteger oldCapcity = _capacity;
    NSMutableArray *newArr = [[NSMutableArray alloc] initWithCapacity:newCapcity];
    for (int i = 0 ; i < [self size]; i ++ ) {
        newArr[i] = _array[i];
    }
    _capacity = newCapcity;
    _array = newArr.mutableCopy;
}
- (BOOL)isNULL:(id)obj{
    if (obj == nil) {
        return YES;
    }
    return NO;
}

-(NSString *)description{
    return _array.description;
}
@end