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 使用例子
定义存储对象
- <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>
定义比较器
- <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>
优先队列的使用
- <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>
输出结果如下:
相关推荐
使用PriorityQueue 使用Deque 使用Stack 使用Iterator 使用Collections IO File对象 InputStream OutputStream Filter模式 操作Zip 读取classpath资源 序列化 Reader Writer PrintStream和...
JAVA:PriorityQueue
PriorityQueue是Java中的一个优先级队列,它可以根据元素的优先级对元素进行排序,并且允许高效地获取和删除最高优先级的元素。
一个简单的待办事项列表应用程序,使用 Realm 作为数据库。
使用C#中的二进制堆的自定义优先级队列实现。为个人/俱乐部项目编写。 (据我所知)它符合大多数.NET标准。不是线程安全的。 信息 这段代码是从Java项目转换为利用C#功能集并在结构上更合理的东西。虽然原始的Java...
优先级队列头文件priorityqueue.h
PriorityQueue-MEX-Matlab 优先级队列 matlab
算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue) 算法面试通关40讲完整课件 11-...
优先队列使用 O(LogN) 复杂度为测试类实现 PriorityQueue。
PriorityQueue 优先队列实现C# PriorityQueueLib: 基于二进制堆的最小/最大优先级队列实现PriorityQueueTests: PriorityQueue单元测试
PriorityQueue PriorityQueue是最小/最大PriorityQueue的Javascript实现。 近期变动 V1.0 在1.0版中,删除了对setComparator(func)和setEquals(func)的支持。 这些方法导致了意外的行为。 需要这些功能时,请...
Java优先队列(PriorityQueue)示例Java开发Java经验技巧共5页.pdf.zip
优先级队列cpp文件PriorityQueue.cpp
主要为大家详细介绍了JDK源码之PriorityQueue,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Lists_Stack_Queue_PriorityQueue.java
主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
优先级队列是一种队列结构,是0个或多个元素的集合,每个元素都有一个优先权,PriorityQueue被内置于JDK中,本文就来解析Java中PriorityQueue优先级队列结构的源码及用法.
NULL 博文链接:https://robblog.iteye.com/blog/566114
主要介绍了java优先队列PriorityQueue中Comparator的用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】