java中的PriorityQueue即优先队列，底层通过数组存储的方式实现了小顶堆

一、PriorityQueue的使用

1.PriorityQueue与其他数据结构的关系

(1)PriorityQueue与其他集合数据结构的继承关系

(2)PriorityQueue实现的方法

2.PriorityQueue的使用

(1)实例化

• new PriorityQueue():使用默认容量和比较器
• new PriorityQueue(int capacity):指定队列的初始化容量
• new PriorityQueue(Comparator<? super E> comparator):指定一个比较器comparator来初始化队列
• new PriorityQueue(int capaicty, Comparator comparator):同时指定初始化容量和比较器
• new PriorityQueue(Collection c):通过一个集合来初始化
• new PriorityQueue(PriorityQueue p):通过另外一个优化队列进行初始化
• new PriorityQueue(SortedSet s):通过一个有序队列来初始化

 /**
* 1.不指定容量和比较器初始化
*/
PriorityQueue<Integer> queue1 = new PriorityQueue<Integer>();
/**
* 2.指定容量初始化
*/
PriorityQueue<Integer> queue2 = new PriorityQueue<Integer>(10);
//只需要实现Comparator的compare方法即可
NumberComparator numberComparator = new NumberComparator();
/**
* 3.通过指定一个比较器初始化
*/
PriorityQueue<Integer> queue3 = new PriorityQueue<Integer>(numberComparator);

(2)添加元素

• add(E e):添加元素e (offer方法也是添加元素)

queue1.add(12);
queue1.add(1);
System.out.println(queue1); //[1, 12]
queue1.add(13);
System.out.println(queue1); //[1, 12, 13]

(3)删除元素

• remove() :删除堆的顶(和poll方法是一样的功能)
• remove(T e):删除指定元素

int removeElement = queue1.remove();
System.out.println(removeElement);  //1
System.out.println(queue1);         //[12, 13]

二、PriorityQueue的实现原理解读

1.PriorityQueue对象

PriorityQueue对象的属性

• queue : 存储数据的数组
• comparator : 比较器对象
• size : 队列长度

2.add方法

public boolean add(E e) {
    //通过调用offer方法来实现的
    return offer(e);
}
public boolean offer(E e) {
  //添加的元素不能为null
  if (e == null)
      throw new NullPointerException();
  modCount++;
  //先定义插入的位置，为队列的长度
  int i = size;
  //如果实际队列占用的长度已经超过数组最大的容量，则需要扩容
  if (i >= queue.length)
      grow(i + 1);
  //增加队列的长度
  size = i + 1;
  //如果队列本来就为空队列，那么插入的元素就是队列的第一个元素
  if (i == 0)
      queue[0] = e;
  else
      //否则，就要通过siftUp函数来进行元素插入
      siftUp(i, e);
  return true;
}
private void siftUp(int k, E x) {
    //如果指定的比较器，就使用比较器来插入
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        //如果没有指定比较器，就使用默认的比较器来插入元素
        siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
    //将插入的元素变为一个可比较的对象
    Comparable<? super E> key = (Comparable<? super E>) x;
    //k为插入的位置(插入节点一直与其父节点进行比较，直到父节点比插入节点小为止)
    while (k > 0) {
        //定义插入的节点的父节点的位置
        int parent = (k - 1) >>> 1;
        //获取父节点的元素值
        Object e = queue[parent];
        //如果插入的值比父节点的值要大，则跳出循环(因为是小顶堆，所以，父节点一定比子节点大，如果父节点比子节点小的话，则需要交换父亲子节点)
        if (key.compareTo((E) e) >= 0)
            break;
        //如果父节点比当前插入的节点值大的话，那么就需要和当前要插入的节点位置进行互换，则当前k的值存储父节点
        queue[k] = e;
        //k的值为原父节点的位置
        k = parent;
    }
    //获取最终节点插入的位置，并存储新元素到这个位置上
    queue[k] = key;
}
private void siftUpUsingComparator(int k, E x) {
    //k为插入的位置(插入节点一直与其父节点进行比较，直到父节点比插入节点小为止)
    while (k > 0) {
        //定义插入的节点的父节点的位置
        int parent = (k - 1) >>> 1;
        //获取父节点的元素值
        Object e = queue[parent];
        //使用指定的比较器来比较插入元素和当前的插入点的父节点元素(比较器都需要实现compare接口)
        if (comparator.compare(x, (E) e) >= 0)
            break;
        //如果父节点比当前插入的节点值大的话，那么就需要和当前要插入的节点位置进行互换，则当前k的值存储
        queue[k] = e;
        //k的值为原父节点的位置
        k = parent;
    }
    //获取最终节点插入的位置，并存储新元素到这个位置上
    queue[k] = x;
}

3.remove方法

```java
public E remove() {
//调用poll方法删除元素
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}

public E poll() {
//如果是空队列，直接返回null
if (size == 0)
return null;
//队列长度减小，并且将s指向最后一个元素
int s = —size;
modCount++;
//获取队列的第一个元素
E result = (E) queue[0];
//获取队列的最后一个元素
E x = (E) queue[s];
//将队列的最后一个位置指向null，即删除最后一个节点
queue[s] = null;
//如果队列原来不只一个元素，使用siftDown来删除节点
if (s != 0)
siftDown(0, x);
//默认是删除第一个节点，则返回第一个节点的元素值
return result;
}

private void siftDown(int k, E x) {
if (comparator != null)
//使用指定的比较器来删除元素
siftDownUsingComparator(k, x);
else
//使用默认的比较器来删除元素
siftDownComparable(k, x);
}

private void siftDownComparable(int k, E x) {
//定义要删除的元素
Comparable<? super E> key = (Comparable<? super E>)x;
//获取中间节点位置
int half = size >>> 1;
while (k < half) {
//删除位置k所在的子节点位置
int child = (k << 1) + 1;
//获取子节点的元素
Object c = queue[child];
//获取右子节点
int right = child + 1;
//如果右子节点不是第后一个元素，而且左子节点比右子节点大
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
//那么左右子节点位置互换
c = queue[child = right];
//如果删除的元素的值比子节点的要小，那么不再交换位置
if (key.compareTo((E) c) <= 0)
break;
//交换父子节点的位置
queue[k] = c;
k = child;
}
//最后找到被删除的节点的位置，将原最后一个节点存入到这个位置上
queue[k] = key;
}