PriorityQueue源码学习

一.初步认识

PriorityQueue的底层实现是基于二叉堆，在进行add(),poll(),removeAt()操作时都会用到堆排序

PriorityQueue可以自定义Comparator，对元素进行比较

PriorityQueue的所有的操作都是线程不安全的，在多线程的场景下，保证线程安全可以使用PriorityBlockingQueue 类。

二.使用方式：

public class StackTest {

public  static  void  main(String  args[]){

PriorityQueue  pq =new PriorityQueue(11,

            new Comparator() {

                @Override

                public int compare(Integer o1, Integer o2) {

                        return o1-o2;

                }

        });

        pq.add(11);

        pq.add(23);

        pq.add(25);

        pq.poll();

        pq.poll();

    }

}

三.方法分析

3.1 add(E e)方法

public boolean add(E e) {

     return offer(e);

}

添加元素的方法调用offer方法实现

3.2offer(E e)方法

public boolean offer(E e) {

    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(i, e);

     return true;

}

元素不能为null，null元素没法进行比较，如果元素的个数超过了初始化的大小，那么就需要进行扩容

如果当时队列中元素个数为0，那么直接赋值，否则就需要进行堆上浮

3.3peek()方法

public E peek() {

    return (size ==0) ?null : (E)queue[0];

}

peek()方法用来获取队列的第一个元素，但是并不清楚元素

3.4remove(Object o)方法

public boolean remove(Object o) {

     int i = indexOf(o);

     if (i == -1)

       return false;

     else {

       removeAt(i);

       return true;

    }

}

首先获取元素的位置，如果元素的不存在返回false，元素存在，迭代移除

3.5clear()方法

public void clear() {

    modCount++;

    for (int i =0; i<size;i++)

        queue[i] =null;

    size =0;

}