1. Introduction

**PriorityQueue**的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器。

• PriorityQueue实现了Queue接口，它实现了Queue的所有方法。
• Java中PriorityQueue实现了_Queue_接口，不允许放入**null**元素。
• 无论是添加新的数据还是取出堆顶的元素，都需要 O(logk) 的时间。
• 其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。
• PriorityQueue是一种无界的，线程不安全的队列。

  2. PQ的使用方法：

  A. Constructor

  PriorityQueue的构造函数支持自定义比较器，如果你反转下比较的逻辑，它也可以是个大顶堆！
  你只需要记住，初始化一个大小为 n 的堆，所需要的时间是 O(n) 即可。 ```java //自然排序 PriorityQueue q = new PriorityQueue();

//通过改造器指定排序规则 PriorityQueue q = new PriorityQueue(new Comparator() { public int compare(Student o1, Student o2) { //按照分数低到高，分数相等按名字 if(o1.getScore() == o2.getScore()){ return o1.getName().compareTo(o2.getName()); } return o1.getScore() - o2.getScore(); } });

//Lambda方式 PriorityQueue q = new PriorityQueue( (s1, s2) -> { if(s1.getScore()==s2.getScore){ return s1.getName().compareTo(s2.getName()); } return s1.getScore() - s2.getScore(); }); ```

B. 常用方法：

• isEmpty()
• size()
• offer()
• poll()

• peek()

  3. PQ的应用场景：

  A. TopK问题

  从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。
  注意：TopK问题的时间复杂度为O(nlogK)。原因是当PQ的size大于K时就应该判断该元素是否能进入PQ。

  B. 贪婪算法：会议室问题

  优先级问题：当每次都只需要在数据中找到最高/最低优先级时，就应该想到PriorityQueue。

  4. PriorityBlockingQueue

  PriorityQueue 是非线程安全的，所以 Java 提供了 PriorityBlockingQueue（实现 BlockingQueue接口）用于Java 多线程环境。

  5. 优先队列数据结构的讲解

  优先队列的本质是一个二叉堆结构。堆在英文里叫 Binary Heap，它是利用一个数组结构来实现的完全二叉树， 即二叉树的顺序存储。

  A. 完全二叉树的性质：

• 一棵具有n个节点的完全二叉树，它的深度为log(n+1)

• 当i=1时, 节点i是二叉树的根
• 如果i>1, 节点i的父节点是i/2
• 若2i<=n, 节点i有左孩子， 左孩子编号是2i；否则节点是叶子节点
• 若2i+1<=n, 节点有右孩子，右孩子编号是2i+1;否则, 节点无右孩子
• 1 - n/2 的节点都是有孩子节点的非叶子节点，其余节点都是叶子节点。

  B. 牢记下面优先队列有三个重要的性质。

1. 数组里的第一个元素 array[0] 拥有最高的优先级别。
   2. 给定一个下标 i，那么对于元素 array[i] 而言：

• 它的父节点所对应的元素下标是 (i-1)/2
• 它的左孩子所对应的元素下标是 2×i + 1
• 它的右孩子所对应的元素下标是 2×i + 2

1. 数组里每个元素的优先级别都要高于它两个孩子的优先级别。

   C. 优先队列最基本的操作有两个。

2. 向上筛选（sift up / bubble up）— offer
   当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部。
   不断进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止。
   时间复杂度：由于二叉堆是一棵完全二叉树，并假设堆的大小为 n，因此整个过程其实就是沿着树的高度往上爬，所以只需要 O(logn) 的时间。
   
   2. 向下筛选（sift down / bubble down）— poll
   当堆顶的元素被取出时，要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作。
   将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。
   时间复杂度：整个过程就是沿着树的高度往下爬，所以时间复杂度也是 O(logk)。
   因此，无论是添加新的数据还是取出堆顶的元素，都需要 O(logk) 的时间。

   D. 初始化

   你只需要记住，初始化一个大小为 n 的堆，所需要的时间是 O(n) 即可。

   6. PQ的实现原理：

   
   
   

   add()和offer()

   add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。
   
   新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为：从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。
   

   remove()和poll()

   remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。
   
   
   该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。