java优先队列PriorityQueue中Comparator的用法详解
在使用java的优先队列PriorityQueue的时候，会看到这样的用法。
PriorityQueuequeue=newPriorityQueue (newComparator (){ @Override publicintcompare(Integero1,Integero2){ returno1.compareTo(o2); } });
那这样到底构造的是最大优先还是最小优先队列呢？
看看源码
看看offer（我也想要offer：X）：
publicbooleanoffer(Ee){
if(e==null){
thrownewNullPointerException();
}else{
++this.modCount;
inti=this.size;
if(i>=this.queue.length){
this.grow(i+1);
}
this.siftUp(i,e);
this.size=i+1;
returntrue;
}
}
1）if和else，分别执行对象判空和容量判断
2）执行siftUp(i,e)，i是原有队列长度，e是要入队的元素。
siftUp是堆中调整元素位置的一种方法，可以看出这里的优先队列是使用最大/最小堆实现的。接着看siftUp：
privatevoidsiftUp(intk,Ex){
if(this.comparator!=null){
siftUpUsingComparator(k,x,this.queue,this.comparator);
}else{
siftUpComparable(k,x,this.queue);
}
}
看看使用了comparator的方法，k是原有队列长度，x是入队元素，queue是队列，comparator是比较器：
privatestaticvoidsiftUpUsingComparator(intk,Tx,Object[]es,Comparatorcmp){ while(true){ if(k>0){ intparent=k-1>>>1; Objecte=es[parent]; if(cmp.compare(x,e)<0){ es[k]=e; k=parent; continue; } } es[k]=x; return; } }
1）k>0，队列长度大于0
2）parent=k-1>>>1;即(k-1)/2，表示最后一个非叶子节点的位置
3）e为父节点，x是入队元素，x可以看做放在最后一个位置。如果compare(x,e)<0，则执行元素往上走的方法。
注：在siftUp中，如果是最小堆，那么应该是较小的元素往上走，如果是最大堆，则应该是较大的元素往上走。
由于源码中新入队元素x是在第1个参数的位置，因此最大/最小优先队列主要根据第1个参数的大小关系来判断。
//对于最大堆，当x>e时，让x上升，则x>e时返回负数，即
intcompare(Integerx,Integere){
returnx>e?-1:1;
}
//对于最小堆，当x
结论：
//最小优先队列，直接returno1.compareTo(o2);
PriorityQueuequeue=newPriorityQueue(newComparator(){
@Override
publicintcompare(Integero1,Integero2){
returno1
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。