publicbooleanoffer(E e){ if (e == null) thrownew 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); returntrue; }
privatevoidsiftUp(int k, E x){ if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }
privatevoidsiftUp(int k, E x){ if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }
@SuppressWarnings("unchecked") privatevoidsiftUpComparable(int k, E x){ Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; }
@SuppressWarnings("unchecked") privatevoidsiftUpUsingComparator(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; }