/**
*
* 優(yōu)先隊(duì)列是用了一種叫做堆的高效的數(shù)據(jù)結(jié)構(gòu)，
* 堆是用二叉樹來描述的，對(duì)任意元素n，索引從0開始，如果有子節(jié)點(diǎn)的話，則左子樹為
* 2*n+1,右子樹為2*(n+1)。
* 以堆實(shí)現(xiàn)的隊(duì)列如果不為空的話，queue[0]即為最小值。
*?
* PS:此優(yōu)先隊(duì)列中的元素并不是升序排列的，只能說是"基本有序"
* 但是queue[0]為樹根而且必定是最小元素
*/
class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {


private static final long serialVersionUID = -7720805057305804111L;


/**
?* 隊(duì)列初始容量大小
?*/
private static final int DEFAULT_INITIAL_CAPACITY = 11;


/**
?* 用來存儲(chǔ)元素的數(shù)組
?*/
public transient Object[] queue;


/**
?* 隊(duì)列中元素個(gè)數(shù)
?*/
private int size = 0;


/**
?*?
?* 比較器，如果為空，則使用元素的自然順序進(jìn)行排序，
?* 反正任意兩元素必須是可比的
?*/
private final Comparator<? super E> comparator;


/**
?*?
?* 隊(duì)列發(fā)生機(jī)構(gòu)性的改變，比如進(jìn)行添加，移除等操作，此變量都會(huì)加1，
?* modCount主要使用來檢測(cè)是否對(duì)隊(duì)列進(jìn)行了并發(fā)操作
?*/
private transient int modCount = 0;


/**
?* 創(chuàng)建一個(gè)初始容量為11的空隊(duì)列
?*/
public PriorityQueue() {
? ? this(DEFAULT_INITIAL_CAPACITY, null);
}


/**
?* 指定隊(duì)列的初始容量，如果initialCapacity<1將拋出
?* IllegalArgumentException異常
?*/
public PriorityQueue(int initialCapacity) {
? ? this(initialCapacity, null);
}


/**
?*?
?* 以指定初始容量與具體比較器對(duì)象的方式創(chuàng)建一個(gè)隊(duì)列
?* 比較器是用來排序的，大家都懂的。
?*/
public PriorityQueue(int initialCapacity,
? ? ? ? ? ? ? ? ? ? ?Comparator<? super E> comparator) {
? ? if (initialCapacity < 1)
? ? ? ? throw new IllegalArgumentException();
? ? this.queue = new Object[initialCapacity]; //數(shù)組初始化
? ? this.comparator = comparator; //比較器初始化
}


/**
?*?
?* 創(chuàng)建一個(gè)包含指定集合c的所有元素的優(yōu)先隊(duì)列，
?* 如果c是一個(gè)SortedSet或另一個(gè)優(yōu)先隊(duì)列，本隊(duì)列中的元素
?* 順序與前者相同，否則按其他比較順序重新排列
?*/
public PriorityQueue(Collection<? extends E> c) {
? ? initFromCollection(c);
? ? if (c instanceof SortedSet) //如果是SortedSet,則獲取它的比較器
? ? ? ? comparator = (Comparator<? super E>)
? ? ? ? ? ? ((SortedSet<? extends E>)c).comparator();
? ? else if (c instanceof PriorityQueue) //如果是PriorityQueue,則獲取它的比較器
? ? ? ? comparator = (Comparator<? super E>) ?
? ? ? ? ? ? ((PriorityQueue<? extends E>)c).comparator();
? ? else {
? ? ? ? comparator = null;
? ? ? ? //從一個(gè)無序序列構(gòu)建一個(gè)堆
? ? ? ? heapify();
? ? }
}


/**
?* 以指定PriorityQueue中的元素，及其Comparator比較器
?* 創(chuàng)建一個(gè)新的優(yōu)先隊(duì)列
?*/
public PriorityQueue(PriorityQueue<? extends E> c) {
? ? comparator = (Comparator<? super E>)c.comparator();
? ? initFromCollection(c);
}


/**
?* 以指定SortedSet中的元素，及其Comparator比較器
?* 創(chuàng)建一個(gè)新的優(yōu)先隊(duì)列
?*/
public PriorityQueue(SortedSet<? extends E> c) {
? ? comparator = (Comparator<? super E>)c.comparator();
? ? initFromCollection(c);
}


/**
?*?
?* 以指定集合中的元素對(duì)數(shù)組進(jìn)行初始化
?*/
private void initFromCollection(Collection<? extends E> c) {
? ? Object[] a = c.toArray();
? ? //如果c.toArray()不能正確的返回一個(gè)數(shù)組對(duì)象，就復(fù)制它為一個(gè)數(shù)組對(duì)象
? ? if (a.getClass() != Object[].class)
? ? ? ? a = Arrays.copyOf(a, a.length, Object[].class);
? ? queue = a; //初始化數(shù)組
? ? size = a.length; //初始化size
}


/**
?*?
?* 動(dòng)態(tài)數(shù)組容量擴(kuò)充的方法
?* @param minCapacity 最小容量
?*/
private void grow(int minCapacity) {
? ? if (minCapacity < 0) // overflow
? ? ? ? throw new OutOfMemoryError();
? ? int oldCapacity = queue.length; //原始容量大小
? ? //如果原始容量小于64則擴(kuò)充為原來的2倍，否則擴(kuò)充為原來的1.5倍
? ? int newCapacity = ((oldCapacity < 64)?
? ? ? ? ? ? ? ? ? ? ? ?((oldCapacity + 1) * 2):
? ? ? ? ? ? ? ? ? ? ? ?((oldCapacity / 2) * 3));
? ? if (newCapacity < 0) // overflow
? ? ? ? newCapacity = Integer.MAX_VALUE;
? ? if (newCapacity < minCapacity)
? ? ? ? newCapacity = minCapacity;
? ? queue = Arrays.copyOf(queue, newCapacity); //這個(gè)方法真好用
}


/**
?*?
?* 向優(yōu)先隊(duì)列中插入一個(gè)元素
?* e為null則則拋出NullPointerException
?* e為不相符的類型則拋出ClassCastException
?* 具體實(shí)現(xiàn)見offer方法
?*/
public boolean add(E e) {
? ? return offer(e);
}




public boolean offer(E e) {
? ? if (e == null)
? ? ? ? throw new NullPointerException();
? ? modCount++; //添加了元素，modCount++
? ? int i = size;
? ? if (i >= queue.length) //如果已經(jīng)添加的元素個(gè)數(shù)已經(jīng)超出了數(shù)組的容量則進(jìn)行容量擴(kuò)充
? ? ? ? grow(i + 1);
? ? size = i + 1;
? ? if (i == 0) //如果添加之前是空隊(duì)列
? ? ? ? queue[0] = e;
? ? else
? ? ? ? siftUp(i, e);
? ? return true;
}


/**
?* 取出最小元素，即根元素，即第1個(gè)元素
?*/
public E peek() {
? ? if (size == 0)
? ? ? ? return null;
? ? return (E) queue[0];
}


/**
?* 由于內(nèi)部是用數(shù)組存儲(chǔ)數(shù)據(jù)，只需要遍歷數(shù)組即可
?*/
private int indexOf(Object o) {
if (o != null) {
? ? ? ? for (int i = 0; i < size; i++)
? ? ? ? ? ? if (o.equals(queue[i]))
? ? ? ? ? ? ? ? return i;
? ? }
? ? return -1;
}


/**
?*?
?* 從隊(duì)列中移除指定元素,如果有多個(gè)，移除第一個(gè)
?* 方法：首先根據(jù)indexOf查找此元素的索引，然后根據(jù)索引移除元素
?*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
? ?return false;
else {
? ?removeAt(i);
? ?return true;
}
}


/**
?* 如果隊(duì)列中存在o則移除它
?*/
boolean removeEq(Object o) {
for (int i = 0; i < size; i++) {
? ? if (o == queue[i]) {
? ? ? ? ? ? removeAt(i);
? ? ? ? ? ? return true;
? ? ? ? }
? ? }
? ? return false;
}


/**
?* 查看隊(duì)列中是否包含o
?*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}


/**
?* toArray
?*/
public Object[] toArray() {
? ? return Arrays.copyOf(queue, size);
}


/**
?* 老方法了，不多說
?*/
public <T> T[] toArray(T[] a) {
? ? if (a.length < size)
? ? ? ? // Make a new array of a's runtime type, but my contents:
? ? ? ? return (T[]) Arrays.copyOf(queue, size, a.getClass());
? ? System.arraycopy(queue, 0, a, 0, size);
? ? if (a.length > size)
? ? ? ? a[size] = null;
? ? return a;
}


/**
?* 返回此隊(duì)列的一個(gè)迭代器
?*/
public Iterator<E> iterator() {
? ? return new Itr();
}


private final class Itr implements Iterator<E> {
? ? /**
? ? ?* 數(shù)組中的索引
? ? ?*/
? ? private int cursor = 0;


? ? /**
? ? ?*?
? ? ?* 最近一次調(diào)用next方法返回的元素的索引
? ? ?* 如果此索引的元素被移除了，重置lastRet為-1
? ? ?*/
? ? private int lastRet = -1;


? ? /**
? ? ?*?
? ? ?* 保存移除元素時(shí)所遇到的特殊情況，
? ? ?* 一般調(diào)用removeAt(int)方法返回的是null，如果值返回不為空則遇到特殊情況
? ? ?* 要將返回的值保存在forgetMeNot隊(duì)列中，cursor大于size時(shí)從forgetMeNot中取
? ? ?* 見removeAt方法
? ? ?*/
? ? public ArrayDeque<E> forgetMeNot = null;


? ? /**
? ? ?* 最后最近一次調(diào)用next方法返回的元素
? ? ?*/
? ? private E lastRetElt = null;


? ? /**
? ? ?* 檢測(cè)是否有并發(fā)操作
? ? ?*/
? ? private int expectedModCount = modCount;


? ? public boolean hasNext() {
? ? ? ? return cursor < size ||
? ? ? ? ? ? (forgetMeNot != null && !forgetMeNot.isEmpty());
? ? }


? ? public E next() {
? ? ? ? if (expectedModCount != modCount)
? ? ? ? ? ? throw new ConcurrentModificationException();
? ? ? ? if (cursor < size)
? ? ? ? ? ? return (E) queue[lastRet = cursor++];
? ? ? ? if (forgetMeNot != null) {
? ? ? ? ? ? lastRet = -1;
? ? ? ? ? ? lastRetElt = forgetMeNot.poll();
? ? ? ? ? ? if (lastRetElt != null)
? ? ? ? ? ? ? ? return lastRetElt;
? ? ? ? }
? ? ? ? throw new NoSuchElementException();
? ? }


? ? public void remove() {
? ? ? ? if (expectedModCount != modCount)
? ? ? ? ? ? throw new ConcurrentModificationException();
? ? ? ? if (lastRet != -1) {
? ? ? ? ? ? E moved = PriorityQueue.this.removeAt(lastRet);
? ? ? ? ? ? lastRet = -1;
? ? ? ? ? ? if (moved == null)
? ? ? ? ? ? ? ? cursor--;
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? if (forgetMeNot == null)
? ? ? ? ? ? ? ? ? ? forgetMeNot = new ArrayDeque<E>();
? ? ? ? ? ? ? ? forgetMeNot.add(moved);
? ? ? ? ? ? }
? ? ? ? } else if (lastRetElt != null) {
? ? ? ? ? ? PriorityQueue.this.removeEq(lastRetElt);
? ? ? ? ? ? lastRetElt = null;
? ? ? ? } else {
? ? ? ? ? ? throw new IllegalStateException();
? ? }
? ? ? ? expectedModCount = modCount;
? ? }
}


public int size() {
? ? return size;
}


/**
?* 移除隊(duì)列中所有元素
?* 移除后隊(duì)列為空
?*/
public void clear() {
? ? modCount++;
? ? for (int i = 0; i < size; i++)
? ? ? ? queue[i] = null;
? ? size = 0;
}


/**
?* 移除第一個(gè)元素(最小的元素)
?* 并重新調(diào)整堆結(jié)構(gòu)
?*/


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


/**
?*?
?* 移除隊(duì)列中的第i個(gè)元素
?* 移除元素時(shí)要重新調(diào)整堆,
?* 移除成功返回值也可能為null
?*/
public E removeAt(int i) {
? ? assert i >= 0 && i < size;
? ? modCount++; //移除元素，隊(duì)列結(jié)構(gòu)改變modCount++
? ? int s = --size;
? ? if (s == i) // 如果是最后一個(gè)元素，直接移除
? ? ? ? queue[i] = null;
? ? else {
? ? ? ? E moved = (E) queue[s]; //這是最后一個(gè)元素
? ? ? ? queue[s] = null; //首先將其設(shè)為null
? ? ? ? /*用i的較小子節(jié)點(diǎn)替換i，即把i移出去，
? ? ? ? ? ? ? ? ? ? ? ? 其子孫節(jié)點(diǎn)依次上升，最后一個(gè)子孫葉子節(jié)點(diǎn)以moved替換*/
? ? ? ? siftDown(i, moved);
? ? ? ??
? ? ? ? /*前面一步已經(jīng)調(diào)整好了堆結(jié)構(gòu)，這一步可能是為了處理特殊情況(我沒遇到過這種特殊情況)
? ? ? ? ? queue[i] == moved，queue[i]是已經(jīng)調(diào)整過的值*/
? ? ? ? if (queue[i] == moved) {
? ? ? ? ? ? siftUp(i, moved);
? ? ? ? ? ? if (queue[i] != moved)
? ? ? ? ? ? ? ? return moved;
? ? ? ? }
? ? }
? ? return null;
}


/**
?* 添加元素后，重新調(diào)整堆的過程，這里從下向上調(diào)整x的位置。
?* 這比初始構(gòu)建堆更簡(jiǎn)單
?*/
private void siftUp(int k, E x) {
? ? if (comparator != null)
? ? ? ? siftUpUsingComparator(k, x);
? ? else
? ? ? ? siftUpComparable(k, x);
}


private void siftUpComparable(int k, E x) {
? ? Comparable<? super E> key = (Comparable<? super E>) x;
? ? while (k > 0) { //<=0就不用調(diào)整了
? ? ? ? int parent = (k - 1) >>> 1; //x的父節(jié)點(diǎn)
? ? ? ? Object e = queue[parent];
? ? ? ? if (key.compareTo((E) e) >= 0) //如果x小于parent則終止調(diào)整
? ? ? ? ? ? break;
? ? ? ? queue[k] = e; //否則父節(jié)點(diǎn)向下移，x為父節(jié)點(diǎn)
? ? ? ? k = parent; //從x處繼續(xù)調(diào)整
? ? }
? ? queue[k] = key;
}


/**
?* 同上
?*/
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;
}


/**
?*
?* 節(jié)點(diǎn)的調(diào)整：從此節(jié)點(diǎn)開始，由上至下進(jìn)行位置調(diào)整。把小值上移。
?* 可以稱之為一次篩選，從一個(gè)無序序列構(gòu)建堆的過程就是一個(gè)不斷篩選的過程.
?* 直到篩選到的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，或其左右子樹均大于此節(jié)點(diǎn)就停止篩選。
?*/
private void siftDown(int k, E x) {
? ? if (comparator != null)
? ? ? ? siftDownUsingComparator(k, x);
? ? else //如果比較器為空，則按自然順序比較元素
? ? ? ? siftDownComparable(k, x);
}


/**
?* 比較器為空的一趟篩選過程。
?* PS:元素必須自己已經(jīng)實(shí)現(xiàn)了Comparable方法
?* 否則將拋出異常
?*/
private void siftDownComparable(int k, E x) {
? ? Comparable<? super E> key = (Comparable<? super E>)x; //父節(jié)點(diǎn)值
? ? int half = size >>> 1; ? ? ? ?// loop while a non-leaf
? ? while (k < half) { //如果還不是葉子節(jié)點(diǎn)
? ? ? ? int child = (k << 1) + 1; //左子節(jié)點(diǎn)索引，先假設(shè)其值最小
? ? ? ? Object c = queue[child];
? ? ? ? int right = child + 1; //右子節(jié)點(diǎn)索引
? ? ? ? if (right < size &&
? ? ? ? ? ? ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) //如果左節(jié)點(diǎn)大于右節(jié)點(diǎn)
? ? ? ? ? ? c = queue[child = right]; //右節(jié)點(diǎn)為最小值
? ? ? ? if (key.compareTo((E) c) <= 0) //如果父節(jié)點(diǎn)小于左右節(jié)點(diǎn)中的最小值，則停止篩選
? ? ? ? ? ? break;
? ? ? ? queue[k] = c; //小值上移
? ? ? ? k = child; //沿著較小值繼續(xù)篩選
? ? }
? ? queue[k] = key; //把最先的父節(jié)點(diǎn)的值插入到正確的位置
}


/**
?* 比較器不為空的一趟篩選過程
?* 一樣的
?*/
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;
}


/**
?* 構(gòu)造初始堆的過程
?*/
private void heapify() {
? ? for (int i = (size >>> 1) - 1; i >= 0; i--) //從最后一個(gè)非終端節(jié)點(diǎn)(size/2 - 1)開始調(diào)整位置
? ? ? ? siftDown(i, (E) queue[i]);
}


/**
?* 返回比較器
?*/
public Comparator<? super E> comparator() {
? ? return comparator;
}


/**
?* 序列化此隊(duì)列
?*/
private void writeObject(java.io.ObjectOutputStream s)
? ? throws java.io.IOException{
? ? // Write out element count, and any hidden stuff
? ? s.defaultWriteObject();


? ? // Write out array length, for compatibility with 1.5 version
? ? s.writeInt(Math.max(2, size + 1));


? ? // Write out all elements in the "proper order".
? ? for (int i = 0; i < size; i++)
? ? ? ? s.writeObject(queue[i]);
}


/**
?* 讀取序列化的文件
?*/
private void readObject(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 = new Object[size];


? ? // Read in all elements.
? ? for (int i = 0; i < size; i++)
? ? ? ? queue[i] = s.readObject();


? ? heapify(); //重新構(gòu)建堆
}
}

總結(jié)

以上是生活随笔為你收集整理的集合框架源码分析六之堆结构的实现(PriorityQueue)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。