优先队列与堆的解析

    队列的特点是先进先出。通常都把队列比喻成排队买东西，大家都很守秩序，先排队的人就先买东西。
    但是优先队列有所不同，它不遵循先进先出的规则，而是根据队列中元素的优先权，优先权最大的先被取出。通常把优先队列比喻成现实生活中的打印。一个打印店里有很多打印机，每台机器的性能不一样，有的打印机打印很快，有的打印机打印速度很慢。当这些打印机陆陆续续打印完自己的任务时进入排队等候状态。如果我这个时候要打印一份文件，我选的不是第一个排队的打印机，而是性能最好，打印最快的打印机。
    优先队列的特点就是将存储的元素根据其优先权的高低，先取出优先权高的元素。所以，优先队列的实现方法有很多。
如果优先权的范围是已知的，那么就可以尝试用一个二维数组来实现优先队列。每一行表示一个优先级别。例如用大小为a[10][10]的二维数组来实现一个优先队列，a[0]表示一个优先级别，里面存放优先级为0的元素，a[10]则存放优先级最高的元素。这样根据元素的优先级进行存储，取出元素的时候，根据优先级，先取出优先级最高的元素。
    上面的方法在优先权范围已知且比较集中可以估计的情况下可以适用，但是如果优先权的范围不清楚，或者间隔很大，就不再使用。实现优先队列也可以用一个链表队列加以实现。链表的节点数据包含两个部分，队列的数据项和该数据项的优先权。将元素存入链表，需要用时，遍历链表，查找优先权最大的数据项。
    还可以用下面的方法。用一个数组来存放优先权，另外一个相应的数组存放要存放的元素。由于，不同的元素可能会有相同的优先权。所以，存放元素的数组中不是直接存放元素，而是存放链表，就像用挂链法来解决哈希冲突一样。当有相同优先权的元素不止一个时，则挂在相应数组索引位置的链表上，如图1。根据优先权数组中存放的优先权，来取得优先权最大的元素。由于数组查找比链表要快，所以，这个方法比上面的方法的改进。

 

Java代码 

private int[] priority   
private ElementNode[] elements   
private int highest   
private int manyItems   
private int PriotityCount  
private int[] priority

private ElementNode[] elements

private int highest

private int manyItems

private int PriotityCount

priority数组是用来存放优先权的，初始的值都是0，之后赋予的优先权值必须都大于0。

Elements是用来存放元素链表的数组。初始值都是null，然后往里面挂上链表。

highest元素是记录优先权最大的元素的数组索引位置，这样，可以方便使用，提高效  率。因为每次要查找优先权最大的元素时，不需要再重新查找。

manyItems用来记录队列中已经存放的元素个数。

PriotityCount用来记录不同优先权的数目。因为有链表的存在，manyItems不能衡量  数组是否满了，而PriotityCount对应的是优先权数组中的使用优先权个数，可以衡量数  组使用情况。

两个私有方法： 

Java代码   

private int getHighest(){}   
private int contains(int priority){}  
private int getHighest(){}

private int contains(int priority){}

     private int getHighest(){}方法是用来取得队列中优先权最大的元素的数组索引位  置。


  private int contains(int priority){}方法是用来查找队列中是否存在指定优先  权。如果存在，返回优先权所在的数组索引位置，如果不存在，则返回-1。

三个公有方法： 

   Java代码   

      public Object getFront(){}   
      public void insert(Object item, int priority){}   
      public Object removeFront(){}  
public Object getFront(){}

public void insert(Object item, int priority){}

public Object removeFront(){}

      public Object getFront(){}方法是用来取得优先权最大的元素的。


     public void insert(Object item, int priority){}方法是用来往队列中添加元素  的。衡量优先权的标准可以很多，这里是直接要求用户在存储元素的时候存储优先权。这个  队列也还没有考虑队列满了以后扩充的情况，所以如果满了会报错。在插入元素时，先要查  看这个元素所对应的优先权是否已经存在，如果已经存在了，那就直接挂到相应数组索引位  置的链表下面。如果不存在，则存放在一个还没有存放值的数组位置中。如果加入元素成  功，要检查是否比原来最大的优先权还要大，如果是，则把highest标记为这个新插入元素  的索引位置。

     public Object removeFront(){}方法是用来删除优先权最大的元素的。删除成功时，  会返回被删除的元素值，否则返回null。删除优先权最大的元素后，还要查找出新的优先  权最大的值，并且让highest指向这个值的索引位置。



示例代码：


Java代码   

package cn.priorityQueue;    
/**  
 * 这个优先队列是基于数组的。  
 * 实现方法是，用两个数组，一个存放元素的权限，另外一个存放元素的值，两个数组的位置相互对应。  
 * 往这个队列中存储元素，需要放入两个值，一个是元素的优先级值，另外一个是元素的值  
 * @author William Job  
 *  
 */  
public class PriorityQueue01 {   
    //这个数组priority用来表示每个元素的优先权   
    private int[] priority;   
    //这个数组element用来存储每个元素的值   
    private ElementNode[] elements;   
    //这个值highest用来指向最高优先权的元素   
    private int highest = 0;   
    //manyItems用来计数已经存储的元素个数   
    private int manyItems;   
    //PriorityCount用来计数已经存储的优先权个数   
    private int PriotityCount;   
       
    public PriorityQueue01(int initialCapacity){   
        priority = new int[initialCapacity];   
        elements = new ElementNode[initialCapacity];   
        manyItems = 0;   
        PriotityCount = 0;   
    }   
       
    /**  
     * 这个方法是用来取得优先权最大的值的。  
     * @throws IllegalAccessException   
     * @return：返回拥有最大优先权的值  
     */  
    public Object getFront(){   
        if(manyItems == 0){   
            throw new IllegalArgumentException("没有元素！");   
        }   
        return elements[highest].element;   
    }              
    /**  
     * 这个方法用来向队列中添加一个元素  
     * 在这个优先队列的实现中，必须同时给定元素的值和元素的优先值  
     * @param item：元素的值  
     * @param priority：元素的优先值，必须大于0  
     * @throws Exception   
     */  
    public void insert(Object item, int priority){   
        if(PriotityCount >= this.priority.length){   
            throw new IllegalArgumentException("队列已满");   
        }   
           
        if(priority <= 0){   
            throw new IllegalArgumentException("优先权必须大于0！");   
        }   
        int add = contains(priority);   
        if(add >= 0){   
            ElementNode node = new ElementNode();   
            node.element = item;   
            node.link = elements[add];   
            elements[add] = node;   
            manyItems ++;   
        }   
        else{   
            ElementNode node = new ElementNode();   
            node.element = item;   
            if(this.priority[PriotityCount] == 0){   
                elements[PriotityCount] = node;   
                   
                add = PriotityCount;   
            }   
            else{   
                for(int j = 0; j < this.priority.length; j ++){   
                    if(this.priority[j] == 0){   
                        add = j;   
                    }   
                }   
                elements[add] = node;   
            }   
            this.priority[add] = priority;   
            manyItems ++;                  
            PriotityCount ++;   
        }   
           
        if(this.priority[add] > this.priority[highest]){   
            highest = add;   
        }   
    }   
       
    /**  
     * 这个方法是用来取得队列中优先权最大的元素的  
     * @return：返回优先权最大的元素的索引位置  
     */  
    private int getHighest(){   
        int index = -1;   
        int temp = 0;   
        for(int i = 0; i < priority.length; i ++){   
            if(priority[i] > temp){   
                temp = priority[i];   
                index = i;   
            }   
        }   
        return index;   
    }               
    /**  
     * 这个方法用来查找队列中是否已经存在这个优先权  
     * @param priority：要查找的优先权  
     * @return：如果这个优先权已经存在则返回这个优先权相应的索引位置，如果不存在则返回-1  
     */  
    private int contains(int priority){   
        int index = -1;   
        for(int i = 0; i < PriotityCount; i ++){   
            if(this.priority[i] == priority){   
                index = i;   
            }   
        }   
        return index;   
    }   
       
    /**  
     * 这个方法用来删除优先权最大的元素，同时返回这个元素。  
     * 当删除这个元素后，如果这个索引位置再也没有相应的元素，则这个索引位置的优先权赋值为0  
     * @return：队列中优先权最大的元素  
     */  
    public Object removeFront(){   
        ElementNode temp = elements[highest];   
        if(elements[highest].link != null){   
            elements[highest] = elements[highest].link;   
        }   
        else{   
            elements[highest] = null;   
            priority[highest] = 0;   
            PriotityCount --;   
        }   
        highest = getHighest();   
        manyItems --;   
        return temp.element;   
    }              
}    
package cn.priorityQueue;   
/**  
 * 这个是元素的节点类。  
 * 这个类中有两个属性：  
 * element存放元素的值，link指向下一个节点  
 * @author William Job  
 *  
 */  
public class ElementNode {   
       
    //元素的值   
    public Object element;   
    //指向下一个元素的地址   
    public ElementNode link;   
    public Object getElement() {   
        return element;   
    }   
    public void setElement(Object element) {   
        this.element = element;   
    }   
    public Object getLink() {   
        return link;   
    }   
    public void setLink(ElementNode link) {   
        this.link = link;   
    }              
}  

 

下一篇是 JDK实现的优先队列PriorityQueue研究

http://luozhong915127.iteye.com/blog/1852306 

评论

1 楼 luozhong915127 2013-04-24  

什么意思，踩别人连个意见都不给。