《恋上数据结构与算法一》笔记（十七）优先级队列

目录

• 优先级队列
• 优先级队列的应用场景举例
• 优先队列的底层实现
• 习题

一 优先级队列

优先级队列也是个队列，因此也是提供以下接口

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

四 习题

• 数组中的第K个最大元素

• 根据字符出现频率排序

• 数据流中的第K大元素

• 有序矩阵中第K小的元素

• 前K个高频元素

• 前K个高频单词

• 查找和最小的K对数字

• 合并K个排序链表

---

项目链接地址 - 17_PriorityQueue

---

本文参考 MJ老师的 恋上数据结构与算法

---

《恋上数据结构与算法一》笔记

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏与点赞是对我最大的支持和鼓励。

---