Java 优先队列 PriorityQueue

1、PriorityQueue概述

Java PriorityQueue 实现了 Queue 接口，不允许放入 null 元素

• 其通过堆实现，具体说是：通过完全二叉树实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue 的底层实现，数组初始大小为11；也可以用一棵完全二叉树表示。
• 优先队列的作用是能保证每次取出的元素都是队列中权值最小的。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较（Comparator，类似于C++的仿函数）。

2、常用方法总结

public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构

public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构

public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出null

public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator<E> iterator(); //迭代器

3、堆结构调整

每次插入或删除元素后，都对队列进行调整，使得队列始终构成最小堆（或最大堆）。

具体调整如下：

• 插入元素后，从堆底到堆顶调整堆；
• 删除元素后，将队尾元素复制到队头，并从堆顶到堆底调整堆。

小根堆结构调整：

• 插入（ add() 和 offer()方法 ）元素后，向上调整堆：
• 删除（ remove() 和 poll()方法 ）元素后，向下调整堆：

4、具体使用

1、实现降序排列

方式一、lambda表达式

PriorityQueue<Integer> queue = new PriorityQueue<>(
    (o1, o2) -> o2 - o1
);

方式二、重写compare方法

PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});

2、实现自定义排序

示例一、按字符串的第三位进行降序排列

PriorityQueue<String> queue = new PriorityQueue<>(
    (o1, o2) -> o2.charAt(2) - o1.charAt(2)
);

示例二、自定义一个类People，先按名字排序，再按年龄排序，再按身高排序

PriorityQueue<People> queue = new PriorityQueue<>(
    (o1, o2) -> {
        if (o1.getName().compareTo(o2.getName()) > 0) {
            return 1;
        } else if (o1.getName().compareTo(o2.getName()) < 0) {
            return -1;
        } else {
            if (o1.getAge() > o2.getAge()) {
                return 1;
            } else if (o1.getAge() < o2.getAge()) {
                return -1;
            } else {
                if (o1.getHeight() - o2.getHeight() > 0) {
                    return 1;
                } else if (o1.getHeight() - o2.getHeight() < 0) {
                    return -1;
                } else {
                    return 0;
                }
            }
        }
    }
);