耿老师教你学Java：优先队列

一、优先队列

优先队列的出列顺序不是按对象的入列顺序，每次出列是优先级别最高的对象。Java 的优先队列 PriorityQueue 使用最小堆管理出列，每次出列是堆顶中的对象，而堆顶（二叉树的根）是最小的对象（可理解为越小级别越高）。进行一次出列或入列操作后，优先队列都要调整堆使得堆顶是级别最高的对象，调整的时间复杂度是 ，其中 是队列的长度，因此优先队列出列和入列的时间复杂度都是 。最小堆是一种特殊的二叉树结构，具体来说是完全二叉树，用于快速找到最小元素。它不是有序树（和 TreeSet 不同，TreeSet 按中序遍历有序输出树中的对象），因为它不满足二叉搜索树的左右子节点有序性要求，其主要特性是堆的性质，即父节点小于或等于子节点的值（父节点的级别高于子节点）。优先队列只是其内部存储结构（堆）的特性决定了元素的存储方式不同于一般的有序数据结构，但始终保持其堆顶元素是优先级最高的元素，当依次执行出列操作时（不属于遍历）是按大小出列的，给人的错觉好像队列是有序集合。

二、java.lang.Comparable接口

1. 队列中的对象需要有一个自然的排序顺序时，该对象应该实现 Comparable<T> 接口，通过实现 compareTo(T t) 方法来规定对象的大小关系。如果对象没有实现 Comparable <T>接口，并且存储在一个需要比较大小的集合中，可能会导致运行时异常或未定义的行为。

2. 创建队列时，可以向构造方法传递一个 Lambda 表达式，该 Lambda 表达式实现了java.util.Comparator 接口（注意不是Comparabl e接口）的int compare（T t1,T t2） 方法，用于重新规定对象的大小关系。

3. 创建队列时，可以向构造方法传递一个 Comparator.reverseOrder 返回的对象，这个对象将按照对象当前的大小关系的反序，确定对象的大小关系。

三、代码

importjava.util.PriorityQueue; importjava.util.Comparator; publicclassTest{ publicstaticvoidmain(String[] args){ PriorityQueue<Integer> queueMin = newPriorityQueue<>; //小的级别高PriorityQueue<Integer> queueMax = newPriorityQueue<>((m,n)->{ if(n>m) return1; elseif(n==m) return0; elsereturn- 1;}); //大的级别高int[] a = { 56, 89, 23, 12, 100, 9, 17}; for( intnum: a ){ queueMin.offer(num); //入列queueMax.offer(num); //入列}System.out.print( "按从小到大出列:"); while(!queueMin.isEmpty){ System.out.print(queueMin.poll+ " "); //出列}System.out.println;System.out.print( "按从大到小出列:"); while(!queueMax.isEmpty){ System.out.print(queueMax.poll+ " "); //出列}System.out.println;PriorityQueue<Student> studentMinMath = newPriorityQueue<>; //数学成绩底，级别高PriorityQueue<Student> studentMaxMath = newPriorityQueue<>(Comparator.reverseOrder); //数学成绩高，级别高PriorityQueue<Student> studentMaxEnglish = newPriorityQueue<>((s1,s2)->{ returns2.englishScore-s1.englishScore;}); //英语成绩高，级别高Student [] student = { newStudent( 56, 89), newStudent( 63, 72), newStudent( 100, 89), newStudent( 77, 58) }; for(Student stu: student){ studentMinMath.offer(stu); //入列studentMaxMath.offer(stu); //入列studentMaxEnglish.offer(stu); //入列

}System.out.println( "输出格式（数学成绩，英语成绩）"); System.out.print( "按数学成绩从低到高出列:"); while(!studentMinMath.isEmpty){ System.out.print(studentMinMath.poll+ " "); //出列}System.out.println;System.out.print( "按数学成绩从高到低出列:"); while(!studentMaxMath.isEmpty){ System.out.print(studentMaxMath.poll+ " "); //出列}System.out.println;System.out.print( "按英语成绩从高到低出列:"); while(!studentMaxEnglish.isEmpty){ System.out.print(studentMaxEnglish.poll+ " "); //出列}}}classStudentimplementsComparable< Student> { intmathScore, englishScore;Student( intmath, intenglish){ mathScore = math;englishScore = english;}publicintcompareTo(Student stu){ returnmathScore-stu.mathScore; //数学成绩低，级别高

}publicString toString{ return"("+mathScore+ ","+englishScore+ ")"; }}