【源码分析篇】堆源码分析

我们先看看文档是如何介绍的：

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

无界的优先队列是基于一个优先堆。优先队列的元素顺序是根据自然排序或者是定制排序的。优先队列不允许元素为null，并且也不允许插入无法比较的对象。

通过分析上诉文档，不难看出，PriorityQueue的构造函数应该有capacity，和Comparator。

我们再来看看offer()方法，因为add()方法调用的是offer()方法，所以我们直接看offer()就可以了。

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;}

首先判断e是否为空，若为空在抛出NPE

再判断是否要进行扩容操作

最后再调用siftUp()方法将元素插入到相应的位置。

grow()方法

private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity);}

扩容的方法比较简单，判断oldCapacity是否小于64，若小于，则在当前基础之上加2，若大于，newCapacity则为oldCapacity的1.5倍，最后重新赋值。

siftUp()方法

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;}

siftUp()底层调用了两个方法，一个是使用比较器的方法，一个是未使用比较器的方法，我们直接看未使用比较器的方法，使用了比较器的方法和未使用比较器的方法差不多。

首先k的parent节点，parent节点的索引时k索引的1/2，在比较新插入的元素与parent节点的值，若大于，则说明当前元素就插入到当前位置，反之，则将parent赋值给k，一次迭代，直至找到插入位置为止。

终上所述，PriorityQueue默认是小根堆（小顶堆）。