Java优先级队列PriotyQueue

优先级队列，顾名思义，和传统“先进后出”的队列相比，优先级队列在元素加入时就根据该元素的优先级插入到相应位置。实际上优先级队列PriotyQueue在poll时还是遵循先进后出，只是数据在进入时已经根据优先级排序了。实现优先级队列需要实现一个Comparator，测试代码如下：

public class PriotyQueueTest { //比较器，，用于判断两个元素的优先级Comparator<Man> t = new Comparator<Man>() {@Overridepublic int compare(Man o1, Man o2) {if(o1.getAge() == o2.getAge())return 0;if(o1.getAge() > o2.getAge())return 1;return -1;}};Queue<Man> queue = new PriorityQueue<Man>(11,t); //将给定数组添加到优先级队列中public void add(int[] nums){for(int i = 0 ; i < nums.length ; i++)queue.add(new Man(String.valueOf(i),nums[i]));} //打印函数public void print(){while(queue.peek()!=null){System.out.println(queue.poll().getAge()+" ");}System.out.println();}public static void main(String[] args) {int[] test = new int[]{5,4,2,3,1};PriotyQueueTest q = new PriotyQueueTest();q.add(test);q.print();}}//测试实体类class Man{private String name;private int age;public Man(String name,int age){this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}} 让我好奇的是，这里的add( )函数中究竟发生了什么？我们把这部分源代码拿出来review一下： private void siftUpUsingComparator(int k, E x) {while (k > 0) {int parent = (k – 1) >>> 1;//下标右移一位，相当于除2Object e = queue[parent];//得到父节点if (comparator.compare(x, (E) e) >= 0)//比较，如果优先级大于父节点则停止向上搜索break;queue[k] = e;k = parent;}queue[k] = x;} 从上面的代码我们可以看到：

1、Queue是基于对象数组实现的，并抽象成树结构；

2、这里的比较器的含义是：直到优先级小于待插元素时停止搜索；

3、删除的时间复杂度为O(1)，插入的时间复杂度为O(n)

生活不会永远都困难;祝你爱情蜜甜，事业大进步

相关文章：

你感兴趣的文章：

标签云：