JDK实现的优先队列PriorityQueue研究

JDK中的java.util.PriorityQueue实现方法不同于上面这些方法，它是基于堆的。

 

    堆本质是一棵二叉树，其中所有的元素都可以按全序语义（参见附录说明）进行比较。用  堆来进行存储需要符合以下规则：

     1.数据集中的元素可以用全序语义进行比较；

     2.每个节点的元素必须大于或小于该节点的孩子节点的元素；

     3.堆是一棵完全二叉树。

 

    用堆来实现优先队列，跟节点始终是优先权最大的元素节点。

 

    插入的思路是这样的，当插入一个元素时。先将这个元素插入到队列尾，然后将这个新插入的元素和它的父节点进行优先权的比较，如果比父节点的优先权要大，则和父节点呼唤位置，然后再和新的父节比较，直到比新的父节点优先权小为止，参见图2和图3

   

 

 

 

 

    这个寻找新插入元素位置的过程对应于java.util.PriorityQueue源代码中的

 

Java代码
Java代码     
 
    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 siftUpComparable(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;     
    }   

Java代码  

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

    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 siftUpComparable(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;

    }

    不是二叉树结构吗？不是节点吗，为什么这里看到的是操作数组？我原来有这样的   疑问，因为之前自己实现过的二叉树只是止于链式结构。然而，树存在如下特点：

 

    1.根节点的数据总是在数组的位置[0]

    2.假设一个非跟节点的数据在数组中的位置[i]，那么它的父节点总是在位置[(i-1)/2]

    3.假设一个节点的数据在数组中的位置为[i]，那么它的孩子（如果有）总是在下面的这两个位置：

         左孩子在[2*i+1]

         右孩子在[2*i+2]

基于这些特点，用数组来表示数会更加方便。源代码中int parent = (k - 1) >>>     1等价于int parent = (k - 1) / 2；对于这里涉及到的位运算，可以参见附录文档。

 

从优先队列中删除优先权最大的元素的思路是将队列尾的元素值赋给跟节点，队列为赋   值为null。然后检查新的根节点的元素优先权是否比左右子节点的元素的优先权大，如果   比左右子节点的元素的优先权小，就交换位置，重复这个过程，直到秩序正常。参见图4