privatevoidreadObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in size, and any hidden stuff s.defaultReadObject(); // Read in (and discard) array length s.readInt(); queue = newObject[size]; // Read in all elements. for (inti=0; i < size; i++) queue[i] = s.readObject();
// Elements are guaranteed to be in "proper order", but the // spec has never explained what that might be. heapify(); }
跟进heapify方法
1 2 3 4
privatevoidheapify() { for (inti= (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); }
跟进siftDown方法
1 2 3 4 5 6
privatevoidsiftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); }
再跟进siftDownUsingComparator方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
privatevoidsiftDownUsingComparator(int k, E x) { inthalf= size >>> 1; while (k < half) { intchild= (k << 1) + 1; Objectc= queue[child]; intright= 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; }