java优先队列PriorityQueue中Comparator的用法详解

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

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
 @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 <T> void siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> 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<e时，让compare(x, e) < 0，即
int compare(Integer x, Integer e){
 return x < e ? -1 : 1; // return x.compareTo(e);
}

结论：

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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Java8 Comparator: 列表排序的深入讲解

    在本文中,我们将看到几个关于如何在Java 8中对List进行排序的示例. 1.按字母顺序排序字符串列表 List<String> cities = Arrays.asList( "Milan", "london", "San Francisco", "Tokyo", "New Delhi" ); System.out.println(cities); //[Milan, london, San

  • 浅析Java中comparator接口与Comparable接口的区别

    Comparable 简介 Comparable 是排序接口. 若一个类实现了Comparable接口,就意味着"该类支持排序".  即然实现Comparable接口的类支持排序,假设现在存在"实现Comparable接口的类的对象的List列表(或数组)",则该List列表(或数组)可以通过 Collections.sort(或 Arrays.sort)进行排序. 此外,"实现Comparable接口的类的对象"可以用作"有序映射(如

  • Java中实现Comparator接口和用法实例（简明易懂）

    在java中,如果要对集合对象或数组对象进行排序,需要实现Comparator接口以达到我们想要的目标. 接下来我们模拟下在集合对象中对日期属性进行排序 一.实体类Step package com.ljq.entity; /** * 运号单流程 * * @author Administrator * */ public class Step{ /** 处理时间 */ private String acceptTime = ""; /** 快件所在地点 */ private String

  • Java8 Comparator排序方法实例详解

    这篇文章主要介绍了Java8 Comparator排序方法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java8 中 Comparator 接口提供了一些静态方法,可以方便于我们进行排序操作,下面通过例子讲解下如何使用 对整数列表排序(升序) List<Integer> list = Arrays.asList(1, 4, 2, 6, 2, 8); list.sort(Comparator.naturalOrder()); Sys

  • Java8 Comparator源码演示及解析

    Java8 Comparator源码演示及解析

    在前面一篇Java Comparable和Comparator对比详解中,对于java中的排序方法进行比较和具体剖析,主要是针对 Comparator接口和 Comparable接口,无论是哪种方式,都需要实现这个接口,并且重写里面的 方法. Java8中对其进行了优化,直接调用Comparator类即可实现一些自定义的排序功能,比如按照某个字段升序,并且按照某个字段降序排列:还有如果出现null 的情况怎么处理等等.下面是针对常见的 基础数据类型的list 和 对象的集合 进行排序的演示. /

  • Java Comparator比较器实例解析

    这篇文章主要介绍了Java Comparator比较器实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 说几点需要注意的,提醒自己即可: 以下是单独定义一个比较器的类,实现了Comparator中的compare方法.(要在Main方法外面定义类噢) 一定是compare而不是Compare哦 package xixixi; import java.util.*; public class Main { public static voi

  • java比较器comparator使用示例分享

    复制代码 代码如下: import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List; public class ComparatorTest implements Comparator<stuEntity> { /**     * @param args     */    public static void main(String[] arg

  • Java 中Comparable和Comparator区别比较

    Comparable 简介Comparable 是排序接口.若一个类实现了Comparable接口,就意味着"该类支持排序".  即然实现Comparable接口的类支持排序,假设现在存在"实现Comparable接口的类的对象的List列表(或数组)",则该List列表(或数组)可以通过 Collections.sort(或 Arrays.sort)进行排序.此外,"实现Comparable接口的类的对象"可以用作"有序映射(如Tre

  • java优先队列PriorityQueue中Comparator的用法详解

    在使用java的优先队列PriorityQueue的时候,会看到这样的用法. PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2){ return o1.compareTo(o2); } }); 那这样到底构造的是最大优先还是最小优先队列呢? 看看源码

  • java 中 ChannelHandler的用法详解

    java 中 ChannelHandler的用法详解 前言: ChannelHandler处理一个I/O event或者拦截一个I/O操作,在它的ChannelPipeline中将其递交给相邻的下一个handler. 通过继承ChannelHandlerAdapter来代替 因为这个接口有许多的方法需要实现,你或许希望通过继承ChannelHandlerAdapter来代替. context对象 一个ChannelHandler和一个ChannelHandlerContext对象一起被提供.一个

  • Java中isAssignableFrom的用法详解

    Java中isAssignableFrom的用法详解

    class1.isAssignableFrom(class2) 判定此 Class 对象所表示的类或接口与指定的 Class 参数所表示的类或接口是否相同,或是否是其超类或超接口.如果是则返回 true:否则返回 false.如果该 Class 表示一个基本类型,且指定的 Class 参数正是该 Class 对象,则该方法返回 true:否则返回 false. 1. class2是不是class1的子类或者子接口 2. Object是所有类的父类 一个例子搞定: package com.auuz

  • java 中的instanceof用法详解及instanceof是什么意思(推荐)

    好,应大家的要求先给大家说下在JAVA程序中instanceof是什么意思 instanceof是Java的一个二元操作符,和==,>,<是同一类东东.由于它是由字母组成的,所以也是Java的保留关键字.它的作用是测试它左边的对象是否是它右边的类的实例,返回boolean类型的数据. instanceof运算符用法 运算符是双目运算符,左面的操作元是一个对象实例,右面是一个类.当左面的对象是右面的类创建的对象时,该运算符运算的结果是true,否则是false 说明: (1).一个类的实例包括本

  • java中stringBuilder的用法详解

    String对象是不可改变的.每次使用System.String类中的方法之一时,都要在内存中创建一个新的字符串对象,这就需要为该新对象分配新的空间.在需要对字符串执行重复修改的情况下,与创建新的String对象相关的系统开销可能会非常昂贵.如果要修改字符串而不创建新的对象,则可以使用System.Text.StringBuilder类.例如,当在一个循环中将许多字符串连接在一起时,使用StringBuilder类可以提升性能. 通过用一个重载的构造函数方法初始化变量,可以创建StringBui

  • java中throws实例用法详解

    在程序出现异常时,会有一个抛出异常的throw出现,这里我们要跟今天所讲的throws区分开.throws的作用是声明抛出,在名称上也跟throw有所不同.下面我们就throws对策概念.语法.实例带来讲解,帮助大家找到声明抛出异常的方法,具体方法如下. 1.概念 如果方法声明的是Exception类型的异常或者是Checked Exception异常,要求方法的调用处必须做处理. (1)继续使用throws向上(方法的调用处)声明 (2)使用try-catch-finally进行处理 2.语法

  • java中DelayQueue实例用法详解

    在阻塞队里中,除了对元素进行增加和删除外,我们可以把元素的删除做一个延迟的处理,即使用DelayQueue的方法.这里的删除需要一定的时间才能生效,有点类似于过期处理的理念.下面我们就DelayQueue的概念.特点进行讲解,然后在代码示例中体会DelayQueue的使用. 1.概念 是一个带有延迟时间的无界阻塞队列.队列中的元素,只有等延时时间到了,才能取出来.此队列一般用于过期数据的删除,或任务调度.以下,模拟一下定长时间的数据删除. 2.特点 (1)无边界设计 (2)添加(put)不阻塞,

  • java中@SuppressWarnings注解用法详解

    SuppressWarnings注解是jse提供的注解.作用是屏蔽一些无关紧要的警告.使开发者能看到一些他们真正关心的警告.从而提高开发者的效率 简介: java.lang.SuppressWarnings是J2SE 5.0中标准的Annotation之一.可以标注在类.字段.方法.参数.构造方法,以及局部变量上.作用:告诉编译器忽略指定的警告,不用在编译完成后出现警告信息. 使用: @SuppressWarnings("") @SuppressWarnings({}) @Suppre

  • Java中instance的用法详解

    关于对象的实例化 大家想到的通常是直接new,除了这个,还有些单实例模式,层次间调用等等 getInstance的使用: * 在主函数开始时调用,返回一个实例化对象,此对象是static的,在内存中保留着它的引用,即内存中有一块区域专门用来存放静态方法和变量, * 可以直接使用,调用多次返回同一个对象. getInstance 和 new的区别: 大部分类都可以用new,new就是通过生产一个新的实例对象,或者在栈上声明一个对象,每部分的调用 *都是用的一个新的对象 getInstance在单例

  • Java中的MapStruct用法详解

    Java中的MapStruct用法详解

    目录 1 MapStruct配置 2 原理&性能 2.1 实现原理 3 使用方法 3.1 转换器的检索 3.1.1 使用Mappers工厂获取 3.1.2 通过依赖注入的方式获取 3.2 简单映射 3.2.1 基本映射 3.2.2 多源参数映射 3.2.3 更新对象 3.3 数据类型转换 3.3.1 对于基础数据类型会进行自动隐式的转换 3.3.2 指定转换格式 3.3.3 属性为复杂对象的映射 3.3.4 自定义转换器 3.3.5 使用限定符限定使用转换方法 3.4 Map的映射 3.5 枚举

随机推荐