堆/堆排序/优先级队列
2022-05-27 本文已影响0人
ZZ_军哥
一.堆的性质
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
