java数据结构－利用Heap（堆）实现PriorityQueue（优先队列）

（一）、首先介绍下优先队列的性质（选自 JDK API）
    优先队列是一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。
   此队列的头 是按指定排序方式确定的最小 元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。
    优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。
    此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。方法 iterator() 中提供的迭代器不 保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray())。
（二）、优先队列中的二叉堆的实现
    从（一）可得知，优先队列是至少允许插入和删除最小者这两个操作的数据结构。
    其中，对于优先队列的实现，二叉堆是很常见的。
    堆是一棵被完全填满的二叉树，可能例外是底层，底层上的元素从左到右依次填入。
而且如果使用数组表示二叉堆，那么对于数组上的任意位置i上的元素，其左儿子的位置是2i，右儿子在左儿子后的单元（2i +1）中，他的父亲则在位置[i/2]上。
    堆的性质，在堆中，对于每一个节点X，X的父亲中的关键字小于或者等于X中的关键字，根节点除外。其中根节点是堆中关键字最小的元素。所以二叉堆的最小元可以在根处找到。
    上滤策略为，现在空闲位置创建一个空穴，如果X可以放在空穴中而不破坏堆排序，那么插入完成，否则，把空穴的父节点上的元素移入空穴中，这样，空穴就朝着根的方向上行进一步，直到可以插入为止。
   附上完全二叉树的一些性质：
如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系：
1、若i = 0, 则 i 无双亲.
2、若i > 0, 则 i 的双亲为：(i -1)/2.?
3、若2*i+1 < n, 则 i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2.
4、若结点编号i为偶数，且i!=0,则左兄弟结点i-1.
5、若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.
6、结点i 所在层次为：log2(i+1)+1

   优先队列是用的堆排序法，算法主要运用在于插入和删除：
   下面的代码为二叉堆的实现

1.	package com.bird.six;  
2.	  
3.	/** 
4.	 * @category 二叉堆的实现 
5.	 * @author Bird 
6.	 * 
7.	 */  
8.	public class BinaryHeap {  
9.	      
10.	    private static final int DEAFAULT_CAPACITY = 100;  
11.	    private int currentSize;//堆中的元素个数   
12.	    private Compare[] array;//存储堆中的元素使用数组存储方式   
13.	      
14.	    public BinaryHeap(){  
15.	        this(DEAFAULT_CAPACITY);  
16.	    }  
17.	      
18.	    public BinaryHeap(int capacity){  
19.	        currentSize = 0;  
20.	        array = new Compare[capacity+1];  
21.	          
22.	    }  
23.	      
24.	    public boolean isEmpty(){  
25.	        return currentSize == 0;  
26.	    }  
27.	      
28.	    public boolean isFull(){  
29.	        return currentSize == array.length-1;  
30.	    }  
31.	      
32.	    public void makeEmpty(){  
33.	        currentSize = 0;  
34.	    }  
35.	      
36.	    /** 
37.	     * 插入使用“上移”法 
38.	     * @param x 
39.	     */  
40.	    public void insert(Compare x){  
41.	        if(isFull())  
42.	            throw new RuntimeException("溢出");  
43.	          
44.	        int hole = ++currentSize;  
45.	        for(; hole >1 && x.compareTo(array[hole/2]) < 0; hole /= 2)  
46.	            array[hole] = array[hole/2];  
47.	        array[hole] = x;   
48.	    }  
49.	      
50.	    /** 
51.	     * 使用下溢法进行删除操作 
52.	     * @return 
53.	     */  
54.	    public Compare deleteMin(){  
55.	        if(isEmpty())  
56.	            return null;  
57.	          
58.	        Compare minItem = array[1];  
59.	        array[1] = array[currentSize--];  
60.	        percolateDown(1);  
61.	          
62.	        return minItem;  
63.	    }  
64.	      
65.	    private void percolateDown(int hole){  
66.	        int child = 0;  
67.	        Compare tmp = array[hole];  
68.	          
69.	        for(; hole * 2 <= currentSize; hole = child){  
70.	            child = hole * 2;  
71.	            if(child != currentSize && array[child+1].compareTo(array[child])<0)  
72.	                child++;  
73.	            if(array[child].compareTo(tmp)<0)  
74.	                array[hole] = array[child];  
75.	            else   
76.	                break;  
77.	        }  
78.	        array[hole] = tmp;  
79.	    }  
80.	}  
81.	  
82.	class Compare implements Comparable<Object>{  
83.	  
84.	    public int compareTo(Object o) {  
85.	        return ((Integer)this.compareTo(o));  
86.	    }  
87.	      
88.	}  

三）、源码解析
1.构造函数的创建

/**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     * 优先级队列代表着一个平衡的二叉堆：队列[n]的两个孩子分别是队列[2*n+1]和队列[2*(n+1)]。
     *先级队列的元素根据构造队列时提供的 Comparator 进行排序，或者按照其自然顺序进行排序：
     *如果比较器为空，则堆中的每一个结点n和它的的子节点d，有n<=d。
     *如果队列不为空的话，则最小值元素是队列[0]。
     */
    private transient Object[] queue;

    /**
     * The number of elements in the priority queue.
     * 优先队列中的元素个数
     */
    private int size = 0;

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     * 优先队列的比较器，如果优先队列按自然排序，则为空
     */
    private final Comparator<? super E> comparator;

    /**
     * The number of times this priority queue has been
     * <i>structurally modified</i>.  See AbstractList for gory details.
     * 该优先队列结构改变的次数，要获取更多细节，请看AbstractList。
     */
    private transient int modCount = 0;

    /**
     * Creates a {@code PriorityQueue} with the default initial
     * capacity (11) that orders its elements according to their
     * {@linkplain Comparable natural ordering}.
     * 使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。
     */
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    /**
     * Creates a {@code PriorityQueue} with the specified initial
     * capacity that orders its elements according to their
     * {@linkplain Comparable natural ordering}.
     ** 使用指定的初始容量创建一个 优先队列，并根据其自然顺序对元素进行排序
     * @param initialCapacity the initial capacity for this priority queue
     * 初始化的容量
     * @throws IllegalArgumentException if {@code initialCapacity} is less
     *  than 1
     * 如果容量小于1，则跑出异常IllegalArgumentException 
     */
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    /**
     * Creates a {@code PriorityQueue} with the specified initial capacity
     * that orders its elements according to the specified comparator.
     *使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。
     * @param  initialCapacity the initial capacity for this priority queue
     * 初始化的容量
     * @param  comparator the comparator that will be used to order this
     *         priority queue.  If {@code null}, the {@linkplain Comparable
     *         natural ordering} of the elements will be used.
     *  用于对此优先级队列进行排序的比较器。如果该参数为 null，则将使用元素的自然顺序 

     * @throws IllegalArgumentException if {@code initialCapacity} is
     *         less than 1
     *         如果容量小于1，则抛出异常IllegalArgumentException 
     */
    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;
    }

    /**
     * Creates a {@code PriorityQueue} containing the elements in the
     * specified collection.  If the specified collection is an instance of
     * a {@link SortedSet} or is another {@code PriorityQueue}, this
     * priority queue will be ordered according to the same ordering.
     * Otherwise, this priority queue will be ordered according to the
     * {@linkplain Comparable natural ordering} of its elements.
     *创建包含指定 collection 中元素的 PriorityQueue。如果指定的 collection 是 SortedSet 的一个实例
     *或者是另一个 PriorityQueue，那么此优先级队列将根据相同顺序进行排序。否则，此优先级队列
     *将根据元素的自然顺序进行排序。 
     * @param  c the collection whose elements are to be placed
     *         into this priority queue
     *         其元素要置于此优先级队列中 

     * @throws ClassCastException if elements of the specified collection
     *         cannot be compared to one another according to the priority
     *         queue's ordering
     *        ClassCastException -如果根据 c 的顺序无法比较 c 中的各个元素 
     * @throws NullPointerException if the specified collection or any
     *         of its elements are null
     *         NullPointerException-如果指定 collection 或任何元素为 null

     */
    public PriorityQueue(Collection<? extends E> c) {
        initFromCollection(c);
        if (c instanceof SortedSet)
            comparator = (Comparator<? super E>)
                ((SortedSet<? extends E>)c).comparator();
        else if (c instanceof PriorityQueue)
            comparator = (Comparator<? super E>)
                ((PriorityQueue<? extends E>)c).comparator();
        else {
            comparator = null;
            heapify();
        }
    }

    /**
     * Creates a {@code PriorityQueue} containing the elements in the
     * specified priority queue.  This priority queue will be
     * ordered according to the same ordering as the given priority
     * queue.
     *创建包含指定优先级队列元素的 PriorityQueue。此优先级队列将根据与给定优先级队列
     *相同的顺序进行排序。 
     *         into this priority queue
     *         有序 set，其元素将置于此优先级队列中 

     * @throws ClassCastException if elements of {@code c} cannot be
     *         compared to one another according to {@code c}'s
     *         ordering
     *         ClassCastException -如果根据 c 的顺序无法比较 c 中的各个元素 


     * @throws NullPointerException if the specified priority queue or any
     *         of its elements are null
     *       NullPointerException-如果指定优先级队列或任何元素为 null


     */
    public PriorityQueue(PriorityQueue<? extends E> c) {
        comparator = (Comparator<? super E>)c.comparator();
        initFromCollection(c);
    }

    /**
     * Creates a {@code PriorityQueue} containing the elements in the
     * specified sorted set.   This priority queue will be ordered
     * according to the same ordering as the given sorted set.
     *创建包含指定有序 set 元素的 PriorityQueue。此优先级队列将根据与给定有序 set 相同的顺序进行排序。 

参数：

     * @param  c the sorted set whose elements are to be placed
     *         into this priority queue
     *         有序 set，其元素将置于此优先级队列中
   
     * @throws ClassCastException if elements of the specified sorted
     *         set cannot be compared to one another according to the
     *         sorted set's ordering
     *   ClassCastException - 如果根据有序 set 的顺序无法比较该有序 set 中的各个元素
     * @throws NullPointerException if the specified sorted set or any
     *         of its elements are null
     *         NullPointerException - 如果指定有序 set 或任何元素为 null

     */
    public PriorityQueue(SortedSet<? extends E> c) {
        comparator = (Comparator<? super E>)c.comparator();
        initFromCollection(c);
    }

2.主要方法的实现（举几个例子，仅供分析。就不一一分析了。）

/**
*将指定的元素插入此优先级队列。
/
public boolean offer(E e) {
    	//如果加入的元素为空，则抛出异常
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        //如果要插入的坐标大于队列长度，队列长度加1
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        //插入元素
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
//获取并移除此队列的头，如果此队列为空，则返回 null。
    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;
    }
// 从此队列中移除指定元素的单个实例（如果存在）。
    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;
    }……

我的个娘啊，真是翻译不完了，暂告一阶段……=

参考资料：
1.JDK API
2.http://blog.csdn.net/a352193394/article/details/7210435
3.http://www.cxyclub.cn/n/12556/

评论

1 楼 shuizhaosi888 2015-01-15  

哎，，惭愧啊！竟然是个女人写的！那，学习了，谢谢分享