Java的优先队列：PriorityQueue

说明：PriorityQueue算法原理就是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）

代码案例：

/**
 * 测试Java的优先队列 PriorityQueue
 * add()和offer()方法，前者在插入失败时抛出异常，后则则会返回false
 * element()和peek()方法，都是获取但不删除队首元素，当方法失败时前者抛出异常，后者返回null，时间复杂度是O(1)
 * remove()和poll() 方法，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null,
 *                 由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整，故时间复杂度是O(n)
 */
@Test
public void testPriorityQueue() {
    //创建多个Goods对象
    List<Goods> goodsList = Lists.newArrayList();
    for (int i = 0; i < 5; i++) {
        Goods goods = new Goods();
        goods.setGoodId((long) i);
        goods.setGoodPrice("50" + i);
        goodsList.add(goods);
    }
    //打乱顺序
    Collections.shuffle(goodsList);
    //打印打乱后的结果
    System.out.println("打乱后的结果：" + JackSonUtil.objToJson(goodsList));
    //定义一个优先队列，并指定价格是比较准则
    PriorityQueue<Goods> priorityQueue = new PriorityQueue<>(Comparator.comparing(Goods ::getGoodPrice));
    //将元素加入进去
    priorityQueue.addAll(goodsList);
    //全部打印这个队列
    System.out.println("priorityQueue = " + JackSonUtil.objToJson(priorityQueue));
    //一个个输出这个队列
    System.out.println("----------priorityQueue一个个弹出-----------");
    System.out.println(JackSonUtil.objToJson(priorityQueue.poll()));
    System.out.println(JackSonUtil.objToJson(priorityQueue.poll()));
    System.out.println(JackSonUtil.objToJson(priorityQueue.poll()));
    System.out.println(JackSonUtil.objToJson(priorityQueue.poll()));
    System.out.println(JackSonUtil.objToJson(priorityQueue.poll()));
    System.out.println(JackSonUtil.objToJson(priorityQueue.poll()));
}

每一次的新加入元素，都会调整这个二叉树，以保证小顶堆特性，poll命令则将顶部的最小元素弹出，而后重新调整二叉树，再次使用poll就会将次小元素弹出，也就是说，本身并不是排序，只有使用的时候才会将顺序弹出。

应用： 可以应用于选择最小、次小、第三小的值产品的情况

参考文章：
《JAVA中PRIORITYQUEUE详解》