数据结构第一季 Day15 优先级队列(Priority Queue)

1、普通队列有什么特点？优先级队列对比普通队列有什么不同？

• 普通队列：符合（先进先出原则，FIFO）
• 优先级队列： 优先取出优先级较高的元素

image.png

2、优先级队列的应用场景举例（至少说出两个）？

• 医院的夜间门诊（会根据病人挂号时间和病情严重程度，做出优先级处理）
• 操作系统的多任务调度系统

3、思考如果基于之前的数据结构，优先级队列使用哪种数据结构实现最佳？

• 当然是二叉堆~~~~~啊啊啊啊啊！！！！

4、基于二叉堆实现的优先级队列代码如下：

package com.lsp.queue;

import com.lsp.heap.BinaryHeap;

import java.util.Comparator;

public class PriorityQueue<E> implements Queue<E> {
    private BinaryHeap<E> binaryHeap;

    public PriorityQueue(Comparator comparator) {
        binaryHeap = new BinaryHeap<>(comparator);
    }

    public PriorityQueue(){
        this(null);
    }

    @Override
    public int size() {
        return binaryHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return binaryHeap.isEmpty();
    }

    @Override
    public void clear() {
        binaryHeap.clear();
    }

    @Override
    public void enQueue(E element) {
        binaryHeap.add(element);
    }

    @Override
    public E deQueue() {
        return binaryHeap.remove();
    }

    @Override
    public E front() {
        return binaryHeap.get();
    }
}