Priority Queue 优先队列

优先队列能够维护出队时的元素最大或最小

什么是优先队列?

优先队列也是一种队列, 同样地主要支持两种操作: 入队 和 出队.

一般的队列满足 FIFO(先进先出) 规则, 而优先队列满足每一次出队的元素 都为整个队列元素的 最小值 或 最大值, 其底层是一个 最小堆 或者是 最大堆

实现一个 最小 优先队列

我们用上一节实现的 最小堆 来实现一个优先队列.

我们定义了一个 优先队列的接口

public interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();

}

然后用定义了一个 MinPriorityQueue 类, 实现了 PriorityQueue 接口, 里面用到了 我们自己写的最小堆 MinHeap

public class MinPriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MinHeap<E> minHeap;
    public MinPriorityQueue(){
        minHeap=new MinHeap<>();
    }

    @Override
    public int getSize() {
        return minHeap.getSize();
    }

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

    @Override
    public void enqueue(E e) {
        minHeap.add(e);
    }

    @Override
    public E dequeue() {
        return minHeap.extractMin();
    }

    @Override
    public E getFront() {
        return minHeap.findMin();
    }

}

可以看出有了 堆 以后, 实现 优先队列 变得非常的简单