实现优先队列

定义并维护一个小顶堆，实现元素的排序（优先队列是按照元素的优先级来决定元素出对的顺序）
定义一个Queue接口，指定PriorityQueue的基本功能
实现PriorityQueue
测试优先队列元素的出栈顺序是否按照元素优先级的顺序

MinHeap小顶堆

实现一个简单的小顶堆（MinHeap） | Feliks

Queue接口

package Queue;

/**
 * todo 定义Queue接口，确定优先队列需要具备的基本功能
 */
public interface Queue<E> {

    /**
     * 获取当前队列大小
     * @return
     */
    int size();

    /**
     * 判断当前队列是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 添加元素到优先队列中
     * @param e
     * @return
     */
    boolean offer(E e);

    /**
     * 返回优先队列优先级最高的元素，如果队列不存在元素则直接返回null
     * @return
     */
    E poll();

    /**
     * 查看优先队列堆顶元素，如果队列为空则直接返回null
     * @return
     */
    E peek();
}

PriorityQueue

package Queue;

import java.util.Comparator;

/**
 * todo 基于前面写好的小顶堆实现优先队列
 */
public class PriorityQueue<E extends Comparable> implements Queue<E> {

    private MinHeap<E> heap;

    /**
     * todo 构造器
     * 1.空参构造器
     * 2.指定比较器的构造器
     */

    // 空参构造器
    public PriorityQueue() {
        heap = new MinHeap<E>();
    }

    // 指定比较器的构造器
    public PriorityQueue(Comparator comparator) {
        heap = new MinHeap<E>(comparator);
    }

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

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

    @Override
    public boolean offer(E e) {
        heap.add(e);
        return true;
    }

    @Override
    public E poll() {
        return heap.poll();
    }

    @Override
    public E peek() {
        return heap.peek();
    }
}

测试优先队列

package Queue;

import java.util.concurrent.ThreadLocalRandom;

public class testPriorityQueue {
    public static void main(String[] args) {
        int n = 1000_0000;
        PriorityQueue<Comparable> priorityQueue = new PriorityQueue<>();

        // 往队列中随机存放一千万个元素
        for (int i = 0; i < n; i++) {
            int element = ThreadLocalRandom.current().nextInt(0, n);
            priorityQueue.offer(element);
        }
        int[] arr = new int[n];

        // 将队列中的元素弹出并存到数组中
        for (int i = 0; i < n; i++) {
            arr[i] = (int) priorityQueue.poll();
        }

        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) {
                throw new RuntimeException("error PriorityQueue");
            }
        }
        System.out.println("优先队列顺序正确！");
    }
}