《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記（十七）優(yōu)先級隊列

一優(yōu)先級隊列

優(yōu)先級隊列也是個隊列觉啊，因此也是提供以下接口

int size(); // 元素的數(shù)量
boolean isEmpty(); // 是否為空 
void enQueue(E element); // 入隊 
E deQueue(); // 出隊
E front(); // 獲取隊列的頭元素 
void clear(); // 清空

普通的隊列是 FIFO 原則屯蹦，也就是

優(yōu)先級隊列則是按照優(yōu)先級高低進行出隊，比如將優(yōu)先級最高的元素作為隊頭優(yōu)先出隊

二優(yōu)先級隊列的應(yīng)用場景舉例

醫(yī)院的夜間門診

隊列元素是病人
優(yōu)先級是病情的嚴重情況完慧、掛號時間

操作系統(tǒng)的多任務(wù)調(diào)度

隊列元素是任務(wù)
優(yōu)先級是任務(wù)類型

三優(yōu)先隊列的底層實現(xiàn)

根據(jù)優(yōu)先隊列的特點柑潦，很容易想到:可以直接利用二叉堆作為優(yōu)先隊列的底層實現(xiàn)

可以通過Comparator 或Comparable 去自定義優(yōu)先級高低

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);
    }
}

打印結(jié)果

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