优先级队列
可以利用二叉堆来实现优先级队列，比如我们用大顶堆，堆顶为我们的最大元素，可以理解为优先级最高的元素，我们优先级队列也是优先级最高的先出对，所以每次从大顶堆取出一个元素，那么这个元素就是优先级最高的，然后相当于最大堆删除了一个元素，然后删除堆顶元素之后，这个堆依然为最大堆，下次再取也是优先级最高的。
代码
//
// SCXPriorityQueue.m
// TestArithmetic
//
// Created by 孙承秀 on 2020/7/7.
// Copyright © 2020 孙承秀. All rights reserved.
//
#import "SCXPriorityQueue.h"
#import "SCXBinaryHeap.h"
@interface SCXPriorityQueue()<SCXBinaryHeapDelegate>
@property (nonatomic , strong) SCXBinaryHeap *heap;
@property (nonatomic , weak) id<SCXPriorityQueueDelegate> delegate;
@end
@implementation SCXPriorityQueue
-(instancetype)initWithDelegate:(id)delegate{
if (self = [super init]) {
self.delegate = delegate;
self.heap = [[SCXBinaryHeap alloc] initWithDelegate:self];
}
return self;;
}
-(NSInteger)size{
return self.heap.size;
}
-(BOOL)isEmpty{
return self.heap.isEmpty;
}
-(void)clear{
[self.heap clear];
}
- (id)deQueue{
return [self.heap removeTopObject];
}
- (void)enQueue:(id)obj{
[self.heap add:obj];
}
-(id)front{
return [self.heap getTopObject];;
}
-(BOOL)compareA:(id)valueA valueB:(id)valueB{
if (self.delegate && [self.delegate respondsToSelector:@selector(compareA:valueB:)]) {
return [self.delegate compareA:valueA valueB:valueB];
}
return YES;
}
-(NSString *)description{
return self.heap.description;
}
@end
堆参考这篇文章
