「优先队列」

应用场景：从序列中找一个最值（最大值或最小值），如果顺序寻找最值需要O(n)的时间，而使用优先队列则只需要O(logn)的时间。

普通的队列是一种先进先出的数据结构，元素在队尾入，在队头出。

在优先队列中。元素被赋予了优先级，具有最高优先级的元素先出。

优先队列是利用堆来实现的，堆可以看作是一棵完全二叉树的循序存储结构，具有n个节点的完全二叉树的深度为（logn）+1

在这棵完全二叉树中，

如果每一个节点的值都大于等于左右孩子的值，则称之为最大堆，大顶堆。

如果每一个节点的值都小于等于左右孩子的值，则称之为最小堆，小顶堆。

优先队列的操作

**出队：**堆顶出队，最后一个记录代替堆顶的位置，重新调整为堆

出队后，除了堆顶之外，其他节点都是满足最大堆的定义，只需要将堆顶执行“下沉”操作，即可调整为堆。

下沉：

堆顶与左右孩子比较，

如果比孩子大，则已满足堆；

如果比孩子小，则与较大的孩子交换，交换到新的位置后，继续向下比较，从根结点一直比较到叶子。

**入队：**新纪录放入最后一个记录之后，重新调整为堆。

入队后，除了新入队记录外，其他节点都满足最大堆的定义，只需要将新纪录执行“上浮”操作，即可调整为堆。

上浮：

新纪录与其双亲比较，

如果小于等于双亲，则已满足堆；

如果比双亲大，则与双亲交换，交换到新的位置后，继续向上比较，从叶子节点一直比较到根。

JDK

PriorityQueue

• PriorityQueue是基于二叉堆原理的优先队列，队列用动态数组实现。
• 它是非阻塞的、非线程安全的；

PriorityQueue内部维护了几个重要属性：

使用：

jdk默认使用的是小顶堆

public static void main(String[] args) {
   PriorityQueue<String> queue = new PriorityQueue<>();
   queue.add("hello");
   System.out.println(queue.peek());
   queue.remove("hello");
   System.out.println(queue.peek());
}

大顶堆：

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

PriorityBlockingQueue

• 是PriorityQueue线程安全版本
• 同样是基于二叉堆的原理，用动态数组实现
• 阻塞的、线程安全的
• 使用ReentrantLock保证线程安全

DelayQueue

• 基于PriorityQueue实现的延迟队列

• 它的删除、插入操作和PriorityQueue基本一致，主要的区别在与poll()、take()等方法。PriorityQueue是只要队列首部有数据就除移，而DelayQueue还需要判断是否达到除移的时间。

• 至于take()、poll()方法的区别在于，take()会阻塞，而poll()直接返回。