集合框架源码分析六之堆结构的实现(PriorityQueue)

有关堆的描述请见我另外一篇博客
http://zhouyunan2010.iteye.com/blog/1217462

/**
*
* 优先队列是用了一种叫做堆的高效的数据结构，
* 堆是用二叉树来描述的，对任意元素n，索引从0开始，如果有子节点的话，则左子树为
* 2*n+1,右子树为2*(n+1)。
* 以堆实现的队列如果不为空的话，queue[0]即为最小值。
* 
* PS:此优先队列中的元素并不是升序排列的，只能说是"基本有序"
* 但是queue[0]为树根而且必定是最小元素
*/
class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {

private static final long serialVersionUID = -7720805057305804111L;

/**
 * 队列初始容量大小
 */
private static final int DEFAULT_INITIAL_CAPACITY = 11;

/**
 * 用来存储元素的数组
 */
public transient Object[] queue;

/**
 * 队列中元素个数
 */
private int size = 0;

/**
 * 
 * 比较器，如果为空，则使用元素的自然顺序进行排序，
 * 反正任意两元素必须是可比的
 */
private final Comparator<? super E> comparator;

/**
 * 
 * 队列发生机构性的改变，比如进行添加，移除等操作，此变量都会加1，
 * modCount主要使用来检测是否对队列进行了并发操作
 */
private transient int modCount = 0;

/**
 * 创建一个初始容量为11的空队列
 */
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

/**
 * 指定队列的初始容量，如果initialCapacity<1将抛出
 * IllegalArgumentException异常
 */
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

/**
 * 
 * 以指定初始容量与具体比较器对象的方式创建一个队列
 * 比较器是用来排序的，大家都懂的。
 */
public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];	//数组初始化
    this.comparator = comparator;		//比较器初始化
}

/**
 * 
 * 创建一个包含指定集合c的所有元素的优先队列，
 * 如果c是一个SortedSet或另一个优先队列，本队列中的元素
 * 顺序与前者相同，否则按其他比较顺序重新排列
 */
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;
        //从一个无序序列构建一个堆
        heapify();
    }
}

/**
 * 以指定PriorityQueue中的元素，及其Comparator比较器
 * 创建一个新的优先队列
 */
public PriorityQueue(PriorityQueue<? extends E> c) {
    comparator = (Comparator<? super E>)c.comparator();
    initFromCollection(c);
}

/**
 * 以指定SortedSet中的元素，及其Comparator比较器
 * 创建一个新的优先队列
 */
public PriorityQueue(SortedSet<? extends E> c) {
    comparator = (Comparator<? super E>)c.comparator();
    initFromCollection(c);
}

/**
 * 
 * 以指定集合中的元素对数组进行初始化
 */
private void initFromCollection(Collection<? extends E> c) {
    Object[] a = c.toArray();
    //如果c.toArray()不能正确的返回一个数组对象，就复制它为一个数组对象
    if (a.getClass() != Object[].class)		
        a = Arrays.copyOf(a, a.length, Object[].class);
    queue = a;		//初始化数组
    size = a.length;	//初始化size
}

/**
 * 
 * 动态数组容量扩充的方法
 * @param minCapacity 最小容量
 */
private void grow(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    int oldCapacity = queue.length;		//原始容量大小
    //如果原始容量小于64则扩充为原来的2倍，否则扩充为原来的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);	//这个方法真好用
}

/**
 * 
 * 向优先队列中插入一个元素
 * e为null则则抛出NullPointerException
 * e为不相符的类型则抛出ClassCastException
 * 具体实现见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)	//如果已经添加的元素个数已经超出了数组的容量则进行容量扩充
        grow(i + 1);
    size = i + 1;
    if (i == 0)		//如果添加之前是空队列
        queue[0] = e;
    else		
        siftUp(i, e);
    return true;
}

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

/**
 * 由于内部是用数组存储数据，只需要遍历数组即可
 */
private int indexOf(Object o) {
	if (o != null) {
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

/**
 * 
 * 从队列中移除指定元素,如果有多个，移除第一个
 * 方法：首先根据indexOf查找此元素的索引，然后根据索引移除元素
 */
public boolean remove(Object o) {
	int i = indexOf(o);		
	if (i == -1)
	    return false;
	else {
	    removeAt(i);
	    return true;
	}
}

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

/**
 * 查看队列中是否包含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;
}

/**
 * 返回此队列的一个迭代器
 */
public Iterator<E> iterator() {
    return new Itr();
}

private final class Itr implements Iterator<E> {
    /**
     * 数组中的索引
     */
    private int cursor = 0;

    /**
     * 
     * 最近一次调用next方法返回的元素的索引
     * 如果此索引的元素被移除了，重置lastRet为-1
     */
    private int lastRet = -1;

    /**
     * 
     * 保存移除元素时所遇到的特殊情况，
     * 一般调用removeAt(int)方法返回的是null，如果值返回不为空则遇到特殊情况
     * 要将返回的值保存在forgetMeNot队列中，cursor大于size时从forgetMeNot中取
     * 见removeAt方法
     */
    public ArrayDeque<E> forgetMeNot = null;

    /**
     * 最后最近一次调用next方法返回的元素
     */
    private E lastRetElt = null;

    /**
     * 检测是否有并发操作
     */
    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;
}

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

/**
 * 移除第一个元素(最小的元素)
 * 并重新调整堆结构
 */

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

/**
 * 
 * 移除队列中的第i个元素
 * 移除元素时要重新调整堆,
 * 移除成功返回值也可能为null
 */
public E removeAt(int i) {
    assert i >= 0 && i < size;
    modCount++;		//移除元素，队列结构改变modCount++
    int s = --size;
    if (s == i) // 如果是最后一个元素，直接移除
        queue[i] = null;
    else {
        E moved = (E) queue[s];	//这是最后一个元素
        queue[s] = null;		//首先将其设为null
        /*用i的较小子节点替换i，即把i移出去，
                        其子孙节点依次上升，最后一个子孙叶子节点以moved替换*/
        siftDown(i, moved);		
        
        /*前面一步已经调整好了堆结构，这一步可能是为了处理特殊情况(我没遇到过这种特殊情况)
          queue[i] == moved，queue[i]是已经调整过的值*/
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

/**
 * 添加元素后，重新调整堆的过程，这里从下向上调整x的位置。
 * 这比初始构建堆更简单
 */
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就不用调整了
        int parent = (k - 1) >>> 1;		//x的父节点
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)	//如果x小于parent则终止调整
            break;
        queue[k] = e;	//否则父节点向下移，x为父节点
        k = parent;		//从x处继续调整
    }
    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;
}

/**
 *
 * 节点的调整：从此节点开始，由上至下进行位置调整。把小值上移。
 * 可以称之为一次筛选，从一个无序序列构建堆的过程就是一个不断筛选的过程.
 * 直到筛选到的节点为叶子节点，或其左右子树均大于此节点就停止筛选。
 */
private void siftDown(int k, E x) {
    if (comparator != null)		
        siftDownUsingComparator(k, x);
    else		//如果比较器为空，则按自然顺序比较元素
        siftDownComparable(k, x);
}

/**
 * 比较器为空的一趟筛选过程。
 * PS:元素必须自己已经实现了Comparable方法
 * 否则将抛出异常
 */
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; //左子节点索引，先假设其值最小
        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;	//把最先的父节点的值插入到正确的位置
}

/**
 * 比较器不为空的一趟筛选过程
 * 一样的
 */
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 heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)		//从最后一个非终端节点(size/2 - 1)开始调整位置
        siftDown(i, (E) queue[i]);
}

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

/**
 * 序列化此队列
 */
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();	//重新构建堆
}
}

评论

1 楼 SW_2011 2012-03-15  

楼主很给力呀