快速入门

Queue是一个严格的先进先出（FIFO）的队列。

但有时候这并不能满足我们的需求。当我们需要对队列中的元素重排，按照重排后的元素顺序出队时，这时候就需要PriorityQueue。

PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。

要使用PriorityQueue，我们就必须给每个元素定义“优先级”。请看下面的例子：

import java.util.PriorityQueue;
import java.util.Queue;

public class MyPriorityQueue {

    public static void main(String[] args) {
        Queue<User> queue = new PriorityQueue<>(
                (User user1, User user2) -> {
                    return user2.getLevel() - user1.getLevel();
                }
        );
        queue.offer(new User("sb_1", 1)); //优先级低
        queue.offer(new User("vip_1", 2)); //优先级高
        while(!queue.isEmpty()) {
            User user = queue.poll();
            System.out.println(user.getName());
        } //出队的顺序是vip_1, sb_1
    }

}

class User{
    private String name;
    private int level;
    public User(String name, int level) {
        this.name = name;
        this.level = level;
    }
    //getter、setter
}

上面的例子使用lambda表达式实现了排序。你也可以自定义排序器（实现Comparable接口），然后将排序器对象传递给PriorityQueue构造器。构造函数签名如下：

public PriorityQueue(Comparator<? super E> comparator)

原理

通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）。

具体请参考堆排序。

快速入门

原理

参考资料