源码解析day06 (PriorityQueue)

简单介绍以及基本参数

PriorityQueue是优先级队列，什么是优先队列呢？ 和先进先出（FIFO）的队列的区别在于，优先队列每次出队的元素都是优先级最高的元素。 PriorityQueue是以数组为基础构成的完全二叉树。

图中的树即为元素的下标构成的，每行排满之后才能排下一行。

基本参数

	/**
	*	构成PriorityQueue的基本数组大小默认为11
	*/
 	private static final int DEFAULT_INITIAL_CAPACITY = 11;
	/**
	*	构成PriorityQueue的基本数组
	*/
    transient Object[] queue; 
    /**
    *  数组中含有的元素多少
    */
    private int size = 0;
    /**
    *  比较规则
    */
    private final Comparator<? super E> comparator;
    /**
    *	数据结构的修改次数
    */
    transient int modCount = 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

构造器

	/**
	*	无参构造器，数组大小为默认值，比较器为null
	*/
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
	/**
	*	会设置数组的初始大小
	*/
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
	/**
	*	会设置数组的初始大小为默认值，比较器为设置的比较器
	*/
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }
	/**
	*	设置初始数组的大小以及比较规则
	*/
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
	/**
	*	将集合添加到PriorityQueue中，排序规则为所填集合的排序值或默认排		   *序方法
	*/
    @SuppressWarnings("unchecked")
    public PriorityQueue(Collection<? extends E> c) {
    //所填集合是否为 SortedSet
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        //所填集合是否为 PriorityQueue
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        //如果都不是
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }
	//将结合加入PriorityQueue
    @SuppressWarnings("unchecked")
    public PriorityQueue(PriorityQueue<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }
	//将结合加入PriorityQueue
    @SuppressWarnings("unchecked")
    public PriorityQueue(SortedSet<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

主要方法讲解

我们会发现构造器中会调用这个方法，那么这个方法的作用是什么呢？

 private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            initFromCollection(c);
        }
    }
  
1
2
3
4
5
6
7
8
9
10

这个方法就是将一个 PriorityQueue中的元素添加到现在的PriorityQueue中，首先会对PriorityQueue进行判空处理，然后将填入的PriorityQueue转化为数组，并重新设置size的值，我们可以看到这里还有另一个方法initFromCollection，那么这个方法又是什么呢

 private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }
1
2
3
4

 private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if (c.getClass() != ArrayList.class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null)
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12

原来在不断的调用其他的方法，那么这个方法又是什么作用呢？
我们可以看到他也是将所填集合转化为数组，同时也可以将类型装换成所填集合的类型。
再来看看扩容方法

  private void grow(int minCapacity) {
  		//获得引用数据类型
        int oldCapacity = queue.length;
        // 如果当前队列长度小于64则扩容2倍，否则扩容1.5倍
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // 判断是否超过最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 赋值数组
        queue = Arrays.copyOf(queue, newCapacity);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

再来看看是如何添加元素的

 public boolean add(E e) {
        return offer(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;
    }
	/**
	*	这个方法里面又调用了其它的两个方法，看看选哪个排序方法添加元素
	*/
  private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

下面我们看一下这连两个方法

 private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
1
2
3
4
5
6
7
8
9
10
11

父节点的左孩子等于 2i+1 右孩子等于2i+2
所以字节点下标 - 1除以2就是父节点的下标，查找到相应位置后进行赋值。

 public void clear() {
        modCount++;
        for (int i = 0; i < size; i++)
            queue[i] = null;
        size = 0;
    }
1
2
3
4
5
6

这个方法是将队列里面的元素都删除

 public E poll() {
 //首先进行元素的判空
        if (size == 0)
            return null;
         //然后数组的长度大小-1
        int s = --size;
        modCount++;
        //返回要删除的元素
        E result = (E) queue[0];
        //获得最后一个元素（最小的元素）
        E x = (E) queue[s];
        
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

该方法是将最前面的元素删除。

  private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        //判断最后一个元素是不是等于该元素
        if (s == i) // removed last element
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除指定位置的元素。