- 1. PriorityQueue中插入对象时的问题
- 2. 对象的比较
- 2.1 覆写基类的equals
- 2.2 基于Comparble接口类的比较
- 2.3 基于比较器比较
- 3. 三种比较方式的对比
- 4. 解决PriorityQueue中插入对象
- 方法1. 利用Comparble接口
- 方法2. 使用比较强对象
优先级队列在插入元素时有个要求:插入的元素不能是null或者元素之间必须要能够进行比较,那么当优先级队列插入自定义对象时,需要怎么处理呢?
看一下代码,它能够正常进行完插入操作吗?
class Card{
public int rank;
public String suit;
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
}
public class Test {
public static void main(String[] args) {
PriorityQueue q = new PriorityQueue<>();
q.offer(new Card(1,"♥"));
q.offer(new Card(2,"♣"));
}
}
答案是:不能。因为优先级队列的底层是堆,插入元素时,为了满足堆的性质,必须进行比较,而目前的Card无法进行比较,因而抛出异常。
下面,将一一介绍对象的几种比较方法。
class Card{
public int rank;
public String suit;
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
@Override
public boolean equals(Object o) {
if (this == o) {//指向同一个对象
return true;
}
if (o == null || o instanceof Card) {//o为空,或者o不是Card的子类
return false;
}
//注意基本类型可以直接比较,但引用类型最好调用其equal方法
Card c = (Card) o;
return rank == c.rank && suit.equals(c.suit);
}
}
注意: 一般覆写 equals 的套路就是上面演示的
- 如果指向同一个对象,返回 true
- 如果传入的为 null,返回 false
- 如果传入的对象类型不是 Card,返回 false
- 按照类的实现目标完成比较,例如这里只要花色和数值一样,就认为是相同的牌
- 注意下调用其他引用类型的比较也需要 equals,例如这里的 suit 的比较
覆写基类equal的方式虽然可以比较,但缺陷是:equal只能按照相等进行比较,不能按照大于、小于的方式进行比较。
2.2 基于Comparble接口类的比较对用用户自定义类型,如果要想按照大小与方式进行比较时:在定义类时,实现Comparble接口即可,然后在类中重写compareTo方法。
class Card implements Comparable2.3 基于比较器比较{ public int rank; public String suit; public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } @Override public int compareTo(Card o) { return rank-o.rank; } public static void main(String[] args) { Card p = new Card(1,"♥"); Card q = new Card(2, "♠"); Card o = new Card(1, "♠"); System.out.println(p.compareTo(q));//小于0,表示p p System.out.println(p.compareTo(o));//等于0,表示牌相等 } }
覆写Comparator中的compare方法
class Card{
public int rank;
public String suit;
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
}
class CardCompartor implements Comparator{
@Override
public int compare(Card o1, Card o2) {
if(o1==o2){
return 0;
}
if(o1==null){
return -1;
}
if(o2==null){
return -1;
}
return o1.rank- o2.rank;
}
}
public class Test {
public static void main(String[] args) {
Card p = new Card(1,"♥");
Card q = new Card(2, "♠");
Card o = new Card(1, "♠");
CardCompartor cmptor = new CardCompartor();// 使用比较器对象进行比较
System.out.println(cmptor.compare(p, o));// == 0,表示牌相等
System.out.println(cmptor.compare(p, q)); // < 0,表示 p 比较小
System.out.println(cmptor.compare(q, p)); // > 0,表示 q 比较大
}
}
3. 三种比较方式的对比
4. 解决PriorityQueue中插入对象 方法1. 利用Comparble接口
- Object.equals 因为所有类都是继承自 Object 的,所以直接覆写即可,不过只能比较相等与否
- Comparable.compareTo 需要手动实现接口,侵入性比较强,但一旦实现,每次用该类都有顺序,属于内部顺序
- Comparator.compare 需要实现一个比较器对象,对待比较类的侵入性弱,但对算法代码实现侵入性强
class Card implements Comparable{ public int rank; public String suit; public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } @Override public int compareTo(Card o) { return rank-o.rank; } @Override public String toString() { return "Card{" + "rank=" + rank + ", suit='" + suit + ''' + '}'; } } public class Test { public static void main (String[] args) { PriorityQueue q =new PriorityQueue<>(); q.offer(new Card(3, "♠")); q.offer(new Card(1,"♥")); q.offer(new Card(2,"♣")); System.out.println(q); } }
上面创建的是小堆,要想创建大堆,只需要将重写的compareTo方法改为:
@Override
public int compareTo(Card o) {
return o.rank-rank;
}
方法2. 使用比较强对象
在实例化优先级队列的时候,传入一个比较器对象即可。
class Card{
public int rank;
public String suit;
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
}
class CardCompartor implements Comparator{
@Override
public int compare(Card o1, Card o2) {
if(o1==o2){
return 0;
}
if(o1==null){
return -1;
}
if(o2==null){
return -1;
}
return o1.rank- o2.rank;
}
}
public class Test {
public static void main(String[] args) {
CardCompartor cmp = new CardCompartor();
PriorityQueue q =new PriorityQueue<>(cmp);
q.offer(new Card(3, "♠"));
q.offer(new Card(1,"♥"));
q.offer(new Card(2,"♣"));
System.out.println(q);
}
}
要想改变堆的特点,只需要在PriorityQueue q =new PriorityQueue<>(cmp)传入相应的比较器对象
也可以在实例化优先级队列时,创建比较器:
public class Test {
public static void main(String[] args) {
CardCompartor cmp = new CardCompartor();
PriorityQueue q =new PriorityQueue<>(new Comparator() {
@Override
public int compare(Card o1, Card o2) {
return o2.rank- o1.rank;
}
});
q.offer(new Card(3, "♠"));
q.offer(new Card(1,"♥"));
q.offer(new Card(2,"♣"));
System.out.println(q);
}
}



