目录
- 优先级队列
- 优先级队列的应用场景举例
- 优先队列的底层实现
- 习题
一 优先级队列
优先级队列也是个队列，因此也是提供以下接口
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void enQueue(E element); // 入队
E deQueue(); // 出队
E front(); // 获取队列的头元素
void clear(); // 清空
普通的队列是 FIFO 原则，也就是
优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队
二 优先级队列的应用场景举例
医院的夜间门诊
- 队列元素是病人
- 优先级是病情的严重情况、挂号时间
操作系统的多任务调度
- 队列元素是任务
- 优先级是任务类型
三 优先队列的底层实现
根据优先队列的特点，很容易想到:可以直接利用二叉堆作为优先队列的底层实现
可以通过Comparator 或Comparable 去自定义优先级高低
- PriorityQueue.m
@implementation PriorityQueue {
BinaryHeap *_heap;
}
- (instancetype)init {
self = [super init];
if (self) {
_heap = [[BinaryHeap alloc] init];
}
return self;
}
- (int)size {
return _heap.size;
}
- (BOOL)isEmpty {
return _heap.isEmpty;
}
- (void)clear {
[_heap clear];
}
- (void)enQueue:(id)element {
[_heap add:element];
}
- (id)deQueue {
return [_heap remove];
}
- (id)front {
return _heap.get;
}
- 测试代码
- (void)test1 {
PriorityQueue *queue = [[PriorityQueue alloc] init];
[queue enQueue:@(2)];
[queue enQueue:@(10)];
[queue enQueue:@(5)];
[queue enQueue:@(15)];
while (!queue.isEmpty) {
NSLog(@"%@",queue.deQueue);
}
}
- 打印结果
2020-03-14 11:23:05.140855+0800 17_PriorityQueue[62348:7767683] 15
2020-03-14 11:23:05.141015+0800 17_PriorityQueue[62348:7767683] 10
2020-03-14 11:23:05.141116+0800 17_PriorityQueue[62348:7767683] 5
2020-03-14 11:23:05.141208+0800 17_PriorityQueue[62348:7767683] 2
四 习题
本文参考 MJ老师的 恋上数据结构与算法
本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏与点赞是对我最大的支持和鼓励。
