PriorityQueue的使用

2024-01-25 19:08

文章标签 使用 priorityqueue

本文主要是介绍PriorityQueue的使用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://blog.csdn.net/yangzhongblog/article/details/8607632

1 概念

优先级队列PriorityQueue是不同于先进先出队列的另一种队列，每次从队列中取出的是具有最高优先权的元素。优先队列可用有序数组或堆实现，但是常用堆来实现，下面是2种实现效率的比较：

使用：用于获取优先权最高的元素。

例如：在1000个数中找到最大的那个数。如果用快速排序对数就行排序，时间复杂度是O(NlogN)；而用优先队列（用队实现）存储数据，然后取出最大元素（此处为优先权最大的元素）这种数据结构时间复杂度为O（logN）。

2 java.util.PriorityQueue方法

java.util.PriorityQueue是从JDK1.5开始提供的新的数据结构接口。如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列。优先级队列不允许 null 元素。其提供的方法如下：

3 使用例子

定义存储对象

[java]  view plain copy 
<span style="font-size:18px;">package zyang.priorityQueue;  
  
/**  
 * Fuction: 
 * @version  2013-2-24 下午8:15:59  
 * @since    1.0  
 */  
  
public class Student {  
      private int number;  
      private String name;  
        
      public Student(int number,String name){  
          this.number=number;  
          this.name=name;  
      }  
  
    public int getNumber() {  
        return number;  
    }  
  
    public void setNumber(int number) {  
        this.number = number;  
    }  
  
    public String getName() {  
        return name;  
    }  
  
    public void setName(String name) {  
        this.name = name;  
    }  
  
    @Override  
    public String toString() {  
        return "Student [number=" + number + ", name=" + name + "]";  
    }   
}  
</span>  

定义比较器

[java]  view plain copy 
<span style="font-size:18px;">package zyang.priorityQueue;  
  
import java.util.Comparator;  
  
/**  
 * Fuction: 
 * 按学号排序 先按学号排序，学号相等时，按姓名排序 o1>o2返回-1，o1=o2返回0，o1<o2返回1  
 * @author    
 * @version  2013-2-24 下午8:16:26  
 * @since    1.0  
 */  
  
public class ComparetorByNumber implements Comparator {  
  
    public int compare(Object o1, Object o2) {  
        Student s1=(Student)o1;  
        Student s2=(Student)o2;  
          
        //compare by number  
        int result=s1.getNumber() > s2.getNumber() ? 1 :(s1.getNumber() == s2.getNumber() ? 0 : -1);  
        //if number is equal, then compare by name  
        if (result==0){  
            int compareByName=s1.getName().compareTo(s2.getName());  
            if(compareByName>0)  
                result=1;  
            else if(compareByName==0)  
                result=0;  
            else  
                result=-1;  
        } //end if  
          
        return (-result); //如果是result,则a>b比较结果后排序是ba，-result代表倒序排序  
    }  
}</span>  

优先队列的使用

[java]  view plain copy 
<span style="font-size:18px;">package zyang.priorityQueue;  
  
import java.util.PriorityQueue;  
  
/**  
 * Fuction: 
 * 
 * @author   yangzhong  E-mail:yangzhonglive@gmail.com 
 * @version  2013-2-24 下午8:15:39  
 * @since    1.0  
 */  
  
public class PriorityQueueApp {  
  
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        PriorityQueue<Student> priorityQueue=new PriorityQueue<Student>(3,new ComparetorByNumber());  
          
        Student[] student={new Student(3,"wangwu"),new Student(2,"lisi"),  
                new Student(5,"xiaowang"),new Student(8,"lihua")};  
          
        for(Student s: student){  
            priorityQueue.offer(s); //use offer() method to add elements to the PriorityQueue   
        }  
          
        System.out.println("size: " + priorityQueue.size()); //print size  
        System.out.println("peek: " + priorityQueue.peek()); //return highest priority element in the queue without removing it  
        System.out.println("size: " + priorityQueue.size()); //print size  
        System.out.println("poll: " + priorityQueue.poll()); //return highest priority element and removes it from the queue  
        System.out.println("size: " + priorityQueue.size()); //print size  
        while(!priorityQueue.isEmpty()) {  
            System.out.print(priorityQueue.poll() + " ");  
        }  
        System.out.println("  the end!");  
    }  
}  
</span>  