怎么在java中使用Comparator方法

怎么在java中使用Comparator方法?很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

创新互联专注为客户提供全方位的互联网综合服务,包含不限于成都网站设计、做网站、冀州网络推广、小程序定制开发、冀州网络营销、冀州企业策划、冀州品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联为所有大学生创业者提供冀州建站搭建服务,24小时服务热线:13518219792,官方网址:www.cdcxhl.com

在使用java的优先队列PriorityQueue的时候,会看到这样的用法。

PriorityQueue queue = new PriorityQueue(new Comparator(){
 @Override
 public int compare(Integer o1, Integer o2){
 return o1.compareTo(o2);
 }
});

那这样到底构造的是最大优先还是最小优先队列呢?

看看源码

看看offer(我也想要offer:X):

public boolean offer(E e) {
    if (e == null) {
      throw new NullPointerException();
    } else {
      ++this.modCount;
      int i = this.size;
      if (i >= this.queue.length) {
        this.grow(i + 1);
      }

      this.siftUp(i, e);
      this.size = i + 1;
      return true;
    }
  }

1)if和else,分别执行对象判空和容量判断
2)执行siftUp(i, e),i是原有队列长度,e是要入队的元素。

siftUp是堆中调整元素位置的一种方法,可以看出这里的优先队列是使用最大/最小堆实现的。接着看siftUp:

private void siftUp(int k, E x) {
    if (this.comparator != null) {
      siftUpUsingComparator(k, x, this.queue, this.comparator);
    } else {
      siftUpComparable(k, x, this.queue);
    }

  }

看看使用了comparator的方法,k是原有队列长度,x是入队元素,queue是队列,comparator是比较器:

private static  void siftUpUsingComparator(int k, T x, Object[] es, Comparator cmp) {
    while(true) {
      if (k > 0) {
        int parent = k - 1 >>> 1;
        Object e = 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时返回负数,即
int compare(Integer x, Integer e){
 return x > e ? -1 : 1;
}
//对于最小堆,当x

结论:

// 最小优先队列,直接 return o1.compareTo(o2);
PriorityQueue queue = new PriorityQueue(new Comparator(){
 @Override
 public int compare(Integer o1, Integer o2){
 return o1 < o2 ? -1 : 1;
 /* e.g., return o1.compare(o2); */
 }
});
// 最大优先队列,则反过来 return o2.compareTo(o1);

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注创新互联行业资讯频道,感谢您对创新互联的支持。


网站题目:怎么在java中使用Comparator方法
网站网址:http://pwwzsj.com/article/pgdcsc.html