堆/堆排序/优先级队列

一.堆的性质
1.本身是个数组,但是用完全二叉树的思想来处理数组内容
2.最大堆的根节点是整个数据中的最大元素,最小堆反之
3.下面所有的例子都是最大堆作为参照
4.父节点的值比子节点的值大

下滤: 当前节点和子节点元素进行比较,如果父节点比子节点要小,那么交换父子节点元素的位置,然后一直将原来的父节点下滤,直至没有比它小的子节点为止
上滤:当前节点和父节点比较,如果当前节点比父节点大,那么交换,直至当前节点不比父节点大

比如下图中的数组元素并不满足堆的性质,需要对数组元素进行建堆操作,以满足堆的性质

1.从最后一个非叶子节点开始下滤,一直持续到根节点,那么整个数组就建好堆了
2.元素索引的关系:比如当前节点的索引为index
左子节点的索引:index * 2+1
右子节点的索引:index * 2+2
父节点的索引:(index+1)/2
3.整个完全二叉树最后一个非叶子节点的索引为
最后一个非叶子节点的索引:count/2-1

例子:比如数组 [ 50,40,60,45,27,12,80,100],按照完全二叉树的排布书序是下面这个样子的

wecom-temp-68cf984c41c3424f854f53a6163ffe6b.png

那么对45下滤的情况,结果为

wecom-temp-d8c8448171a4392b68491e979751456e.png
再对60下滤的效果
wecom-temp-ae1f6afa2a6e6e7bd42d6024e83907ae.png

再对40下滤的效果

wecom-temp-4a22b18cef7f8c1380c5ac9bc5537910.png
再对50下滤的效果
wecom-temp-c4fc5bd16bde0b0ed49fb40787e9e8af.png

最后这个数组就建好了一个最大堆, [100,50,80,45,27,12,60,40]

A.原地建堆并且下滤的代码,通过这段代码就完成了数组建堆操作

//上滤
- (void)siftUp:(NSInteger)index
{
    if (index>=_heapArray.count) return;
    id obj = _heapArray[index];
    while(index>0){
        //获取父元素
        NSInteger parentIndex = (index-1)>>1;
        id parent = _heapArray[parentIndex];
        if (parentIndex>=0 &&_compareBlock(obj,parent)<=0) break;
        _heapArray[index] = parent;
        index = parentIndex;
    }
    _heapArray[index] = obj;
}
//原地建堆
- (void)createHeapArray
{
    NSInteger count = _heapArray.count;
    for (NSInteger index = (count>>1)-1; index>=0; index--) {
        [self siftDown:index];
    }
}

B.添加元素后,对最后一个元素进行上滤操作,以维持整个堆的性质

//上滤
- (void)siftUp:(NSInteger)index
{
    if (index>=_heapArray.count) return;
    id obj = _heapArray[index];
    while(index>0){
        //获取父元素
        NSInteger parentIndex = (index-1)>>1;
        id parent = _heapArray[parentIndex];
        if (parentIndex>=0 &&_compareBlock(obj,parent)<=0) break;
        _heapArray[index] = parent;
        index = parentIndex;
    }
    _heapArray[index] = obj;
}

C.删除元素时,移除根元素,并将最后一个元素替换掉根元素,然后对根元素进行下滤,以维持堆的性质

//移除顶部元素
- (NSObject *)removeElementAtTop
{
    if (_heapArray.count==0) return nil;
    if (_heapArray.count==1) {
        NSObject *obj = _heapArray[0];
        [_heapArray removeAllObjects];
        return obj;
    }
    //如果存在多个元素,将最后一个元素替换掉0的位置,并且最后一个置为空,同时第一个元素下滤
    NSObject *fristObj = _heapArray[0];
    NSObject *lastObj = [_heapArray lastObject];
    _heapArray[0] = lastObj;
    [_heapArray removeLastObject];
    [self siftDown:0];
    return fristObj;
}

二.堆排序

1.原理:在我们对数组元素建完堆后,根节点的元素最大,那么我们将根节点和最后一个节点进行交换,然后再对根节点进行下滤,并且将之前找到的最大值排除在外,重复执行此操作,那么整个数组就排好序了

typedef NSInteger(^SortBlock)(NSObject *obj1,NSObject *obj2);
+ (NSArray *)heapSort:(NSArray *)dataArray compareBlock:(SortBlock)sortBlock;

+ (NSArray *)heapSort:(NSArray *)dataArray compareBlock:(SortBlock)sortBlock
{
    if (dataArray==nil || dataArray.count<=1) return dataArray;
    NSMutableArray *marr = dataArray.mutableCopy;
    NSInteger heapCount = marr.count;
    //1.原地建堆:完全二叉树将数组元素逐个填充到完全二叉树,从倒数第一个非叶子节点进行下滤操作,那么最终,第一个元素一定是最大值
    for (NSInteger index = (marr.count>>1)-1; index>=0; index--) {
        [self siftDown:index dataArray:marr compareBlock:sortBlock count:heapCount];
    }
    //2.将第一个最大元素和最后面的那个元素进行交换,再对交换后的元素进行下滤操作,并缩小最大堆的范围,循环执行此操作,那么最中数组就排好序列了
    while (heapCount>1) {
        --heapCount;
        [self swapIndex1:0 index2:heapCount dataArray:marr];
        [self siftDown:0 dataArray:marr compareBlock:sortBlock count:heapCount];
    }
    return marr.copy;
}
//下滤
+ (void)siftDown:(NSInteger)index dataArray:(NSMutableArray *)dataArray compareBlock:(SortBlock)sortBlock count:(NSInteger)count
{
    id markObj = dataArray[index];
    NSInteger half = count>>1;
    while (index<half) {
        NSInteger childIndex = (index<<1)+1;
        id child = dataArray[childIndex];
        NSInteger rightIndex = childIndex+1;
        if (rightIndex<count && sortBlock(dataArray[rightIndex],child)>0) {
            childIndex = rightIndex;
            child = dataArray[childIndex];
        }
        if (sortBlock(markObj,child)>=0) break;
        dataArray[index] = child;
        index = childIndex;
    }
    dataArray[index] = markObj;
}

三.优先级队列
1.比如医院来病人了,那么治疗顺序肯定要按紧急程度治疗,总不能别人都快挂了还要排个队等前面的感冒啥的完了之后再治疗
2.利用堆来实现优先级队列的代码

下面是完整的堆代码

typedef NSInteger(^HeapCompareBlock)(NSObject *obj1,NSObject *obj2);

@interface GYJHeap : NSObject

//堆中元素数量
@property(nonatomic,readonly)NSInteger size;
//指定的构造方法,必须传入对象的比较方式,数据内容可以先不传,后面加
- (instancetype)initWithDefaultArray:(nullable NSArray *)defaultArray CompareBlock:(HeapCompareBlock NS_NOESCAPE)compareBlock;
//给堆原来的基础上添加元素
- (void)continueAddElements:(NSArray *)elements;
//添加一个元素
- (void)addElement:(NSObject *)obj;
//堆是否为空
- (BOOL)isEmpty;
//清空堆
- (void)clear;
//查看最顶部的元素
- (NSObject *)lookTowerTopElement;
//移除顶部元素
- (NSObject *)removeElementAtTop;

@end

#import "GYJHeap.h"

@interface GYJHeap()

@property(nonatomic,strong)NSMutableArray *heapArray;
//元素与元素间比较的block,以确定对象大小关系
@property(nonatomic,copy)HeapCompareBlock compareBlock;

@end

@implementation GYJHeap

//构造方法,必须传入对象的比较方式
- (instancetype)initWithDefaultArray:(nullable NSArray *)defaultArray CompareBlock:(HeapCompareBlock NS_NOESCAPE)compareBlock
{
    if (self = [super init]) {
        _compareBlock = compareBlock;
        if (defaultArray==nil) {
            _heapArray = [[NSMutableArray alloc]init];
        }else{
            _heapArray = defaultArray.mutableCopy;
            [self createHeapArray];
        }
    }
    return self;
}
- (instancetype)init
{
    if (self = [super init]) {
        NSAssert(NO, @"不要使用这个init方法初始化堆,使用另外一个");
    }
    return self;
}
//给堆中添加元素
- (void)continueAddElements:(NSArray *)elements
{
    if (elements==nil || elements.count==0) return;
    for (NSInteger i = 0; i<elements.count; i++) {
        [self addElement:elements[i]];
    }
}
//添加一个元素
- (void)addElement:(NSObject *)obj
{
    if (obj==nil) return;
    [_heapArray addObject:obj];
    [self siftUp:_heapArray.count-1];
}
//堆是否为空
- (BOOL)isEmpty
{
    return _heapArray.count==0?YES:NO;
}
//清空堆
- (void)clear
{
    [_heapArray removeAllObjects];
}
//查看最顶部的元素
- (NSObject *)lookTowerTopElement
{
    return _heapArray.count>0?_heapArray[0]:nil;
}
//移除顶部元素
- (NSObject *)removeElementAtTop
{
    if (_heapArray.count==0) return nil;
    if (_heapArray.count==1) {
        NSObject *obj = _heapArray[0];
        [_heapArray removeAllObjects];
        return obj;
    }
    //如果存在多个元素,将最后一个元素替换掉0的位置,并且最后一个置为空,同时第一个元素下滤
    NSObject *fristObj = _heapArray[0];
    NSObject *lastObj = [_heapArray lastObject];
    _heapArray[0] = lastObj;
    [_heapArray removeLastObject];
    [self siftDown:0];
    return fristObj;
}
- (NSInteger)size;
{
    return _heapArray.count;
}
//下滤
- (void)siftDown:(NSInteger)index
{
    if (index>=_heapArray.count) return;
    id obj = _heapArray[index];
    NSInteger halfIndex = _heapArray.count>>1;
    while (index<halfIndex) {
        //获取左子元素
        NSInteger childIndex = (index<<1)+1;
        id child = _heapArray[childIndex];
        NSInteger rightIndex = childIndex+1;
        //比较左右子元素,确定那个是最大的子元素
        if (rightIndex<_heapArray.count &&_compareBlock(_heapArray[rightIndex],child)>0) {
            child = _heapArray[rightIndex];
            childIndex = rightIndex;
        }
        //如果本身比左右子元素大,那么直接退出
        if (_compareBlock(obj,child)>=0) break;
        _heapArray[index] = child;
        index = childIndex;
    }
    _heapArray[index] = obj;
}
//上滤
- (void)siftUp:(NSInteger)index
{
    if (index>=_heapArray.count) return;
    id obj = _heapArray[index];
    while(index>0){
        //获取父元素
        NSInteger parentIndex = (index-1)>>1;
        id parent = _heapArray[parentIndex];
        if (parentIndex>=0 &&_compareBlock(obj,parent)<=0) break;
        _heapArray[index] = parent;
        index = parentIndex;
    }
    _heapArray[index] = obj;
}
//原地建堆
- (void)createHeapArray
{
    NSInteger count = _heapArray.count;
    for (NSInteger index = (count>>1)-1; index>=0; index--) {
        [self siftDown:index];
    }
}
@end

下面是优先级队列的代码

@interface GYJPriorityQueue : NSObject

//构造方法
- (instancetype)initWithCompareBlock:(HeapCompareBlock)compareBlock;
//元素数量
@property(nonatomic,readonly)NSInteger count;
//批量入队
- (void)enterPriorityQueueDefaultElements:(NSArray *)elements;
//单个入队
- (void)enterPriorityQueue:(NSObject *)element;
//队列是否为空
- (BOOL)isEmpty;
//清空队列
- (void)clear;
//出队最大或者最小权重的元素
- (NSObject *)outPriorityQueue;
//即将出队的元素
- (NSObject *)willOutPriorityQueueElement;

@end

#import "GYJPriorityQueue.h"

@interface GYJPriorityQueue ()

@property(nonatomic,strong)GYJHeap *heap;

@end

@implementation GYJPriorityQueue
//构造方法
- (instancetype)initWithCompareBlock:(HeapCompareBlock)compareBlock
{
    if (self = [super init]) {
        _heap = [[GYJHeap alloc]initWithDefaultArray:nil CompareBlock:compareBlock];
    }
    return self;
}
- (instancetype)init
{
    if (self = [super init]) {
        NSAssert(NO, @"请使用指定的优先级队列构造方法,不要使用init");
    }
    return self;
}
- (NSInteger)count
{
    return _heap.size;
}
//批量入队
- (void)enterPriorityQueueDefaultElements:(NSArray *)elements
{
    [_heap continueAddElements:elements];
}
//单个入队
- (void)enterPriorityQueue:(NSObject *)element
{
    [_heap addElement:element];
}
//队列是否为空
- (BOOL)isEmpty
{
    return _heap.size==0?YES:NO;
}
//清空队列
- (void)clear
{
    [_heap clear];
}
//出队最大或者最小权重的元素
- (NSObject *)outPriorityQueue
{
    return [_heap removeElementAtTop];
}
//即将出队的元素
- (NSObject *)willOutPriorityQueueElement
{
    return [_heap lookTowerTopElement];
}
@end