// 3 // 这里是走到 4 的构造方法去了 public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); }
// 4 /** 可以看到前面的三个都是走到了这里来了, 长度如果是小于1的话,就会报错. this.queue 的数组长度就是 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 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }
/** 这里可以看到,如果值是null的话,就会抛出NPE的异常. 如果size的大小比 queue数组的长度还大的话,就会进行扩容. 然后size长度+1,如何i是0的话,就说明是第一个元素,不需要任何拍寻处理,直接赋值给第一个即可. 如果不是第一个的话,就会走siftUp方法 */ 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; }
public E peek() { return (size == 0) ? null : (E) queue[0]; }
remove 方法 :
/** 删除元素的方法。 indexOf 如果返回的不是-1的话,就说明是有值得,就会走到 removeAt 方法 */ public boolean remove(Object o) { int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } }
/** indexOf 这个方法就是判断在这个集合里面有没有 o 这个值, 如果有的话就会返回对应的下标,如果不存在的话,就会返回-1的值 */ private int indexOf(Object o) { if (o != null) { for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; } return -1; }
/** removeAt 方法就会将传入进来的i的下标的值重置为null,这是满足 i == --size 的情况下. 然后会将要删除的下标 i 和 对应的值 moved 传入到 siftDown 这个方法中. siftUp()是在前面有讲解到的. 这里还是很明显的看到, priorityQueue是一直在维护这排序的关系。 */ 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; }
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; }
private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least 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; }
