1.类的定义
public class PriorityQueue<E> extends AbstractQueue<E>implements java.io.Serializable2.基本成员变量
1.序列化所需
private static final long serialVersionUID = -7720805057305804111L;2.默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;3.对象数组(用来存储数据)
private transient Object[] queue;4.表示当前长度
private int size = 0;5.对比器
private final Comparator<? super E> comparator;6.修改次数
private transient int modCount = 0;7.最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;3.构造方法
1.无参构造
public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}调用了两个参数的构造方法 直接传入默认长度
2.initialCapacity构造
public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}调用两个参数的构造方法 传入initialCapacity
3.initialCapacity,comparator
public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {// Note: This restriction of at least one is not actually needed,// but continues for 1.5 compatibilityif (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}4.Collection构造
public PriorityQueue(Collection<? extends E> c) {if (c instanceof SortedSet<?>) {SortedSet<? extends E> ss = (SortedSet<? extends E>) c;this.comparator = (Comparator<? super E>) ss.comparator();initElementsFromCollection(ss);}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);}}根据传进去不同的Collection进行不同的处理
5.PriorityQueue构造
public PriorityQueue(PriorityQueue<? extends E> c) {this.comparator = (Comparator<? super E>) c.comparator();initFromPriorityQueue(c);}6.SortedSet构造
public PriorityQueue(SortedSet<? extends E> c) {this.comparator = (Comparator<? super E>) c.comparator();initElementsFromCollection(c);}4.initFromPriorityQueue
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {//如果是PriorityQueue类型直接将数组和size复制过去即可if (c.getClass() == PriorityQueue.class) {this.queue = c.toArray();this.size = c.size();} else {initFromCollection(c);}}通过PriorityQueue初始化
5.initElementsFromCollection
private void initElementsFromCollection(Collection<? extends E> c) {Object[] a = c.toArray();// If c.toArray incorrectly doesn't return Object[], copy it.if (a.getClass() != Object[].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;}
通过Collection初始化的时候需要进行一些前期处理，最后再进行赋值
6.initFromCollection
private void initFromCollection(Collection<? extends E> c) {initElementsFromCollection(c);heapify();}通过Collection初始化先复制数组和size再进行调整
7.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));//可以看出当容量小于64的时候扩容方式为2old+2 当 大于64的时候为1.5old// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}扩容
8.hugeCapacity
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}返回其最大容量
9.add
public boolean add(E e) {return offer(e);}调用offer添加元素
10.offer
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;//如果容量为0直接放入到0号下标if (i == 0)queue[0] = e;else//如果不是就需要进行调整siftUp(i, e);return true;}添加元素
11.peek
public E peek() {if (size == 0)return null;return (E) queue[0];}返回队列最前面的值，如果没有返回null
12.indexOf
private int indexOf(Object o) {if (o != null) {for (int i = 0; i < size; i++)if (o.equals(queue[i]))return i;}return -1;}查找到对象的索引
13.remove(obj)
public boolean remove(Object o) {int i = indexOf(o);if (i == -1)return false;else {removeAt(i);return true;}}删除某个对象
14.removeEq
boolean removeEq(Object o) {for (int i = 0; i < size; i++) {if (o == queue[i]) {removeAt(i);return true;}}return false;}删除某个对象，通过循环遍历
15.contains
public boolean contains(Object o) {return indexOf(o) != -1;}直接查其索引如果没查到说明没有
16.size
public int size() {return size;}获得长度
17.clear
public void clear() {modCount++;for (int i = 0; i < size; i++)queue[i] = null;size = 0;}清空整个队列
18.poll
public E poll() {if (size == 0)return null;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;}返回队列的头元素并且删除
19.removeAt
private E removeAt(int i) {assert i >= 0 && i < size;modCount++;int s = --size;//如果删除的最后一个元素直接置null即可if (s == i) // removed last elementqueue[i] = null;else {//先获取到最后一个数据E moved = (E) queue[s];//置为nullqueue[s] = null;//将最后一个数据放置到i号位置并且调整siftDown(i, moved);//如果第i号位置还是movedif (queue[i] == moved) {siftUp(i, moved);if (queue[i] != moved)return moved;}}return null;}删除某个下标下的数据(其实相当于把最后一个元素放置到i位置并且调整即可)
20. siftUp
private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}从下往上调整
21.siftUpComparable
private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {//找到其父节点int parent = (k - 1) >>> 1;Object e = queue[parent];//x和父节点进行比较，如果符合条件就直接跳出if (key.compareTo((E) e) >= 0)break;//不符合的话需要将父节点放到当前位置queue[k] = e;//然后向上移动k = parent;}最后将需要调整的值放入到k位置queue[k] = key;}当没有比较器的时候的调整过程
22.siftUpUsingComparator
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;}当使用比较器时候的调整过程
23.siftDown
private void siftDown(int k, E x) {if (comparator != null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x);}从上往下调整
24.siftDownComparable
private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>)x;int half = size >>> 1; // loop while a non-leafwhile (k < half) {//先找到符合条件的一个孩子int child = (k << 1) + 1; // assume left child is leastObject 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;}当不使用比较器时候的调整过程
25.siftDownUsingComparator
private void siftDownUsingComparator(int k, E x) {int half = size >>> 1;while (k < half) {int child = (k << 1) + 1;Object c = queue[child];int right = child + 1;if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0)c = queue[child = right];if (comparator.compare(x, (E) c) <= 0)break;queue[k] = c;k = child;}queue[k] = x;}当使用比较器时候的调整过程
26.heapify
private void heapify() {for (int i = (size >>> 1) - 1; i >= 0; i--)siftDown(i, (E) queue[i]);}调整整个队列,从下往上调整，每次只调整一个小树
27. Comparator
public Comparator<? super E> comparator() {return comparator;}获得比较器