目录
- Java优先队列PriorityQueue的各种打开方式以及一些你不知道的细节
- 优先队列的默认用法—从小到大排序
- 对String类用优先队列从大到小排序
- 通过自定义比较器对自定义的类进行从小到大排序
- 通过自定义的类实现Comparable接口进行从大到小排序
- 用lambda表达式优化比较器的使用
Java优先队列PriorityQueue的各种打开方式以及一些你不知道的细节
未经作者允许,不可转载,如有错误,欢迎指正o( ̄▽ ̄)o
- 首先我们知道用PriorityQueue这个类创建的对象是一个集合,然后调用api可以将一个个对象添加入集合,然后再通过api遍历时,插入的元素就从小到大排序输出,真的太神奇了!
- 下面将介绍优先队列的默认用法以及我想自己写个类,然后扔到优先队列中让它也能从小到大排序怎么做?从大到小嘞?又或者我又想用系统的类比如String,但是我想按字典序从大到小能做吗?
- 题外话:每插入一个就会自动排序,这么强大的功能,效率一定不高吧?但如果你学过数据结构,想一下建堆的过程,以及堆排序中添加与调整堆的过程你就会发现,堆排序与优先队列每次插入排序的功能是那么契合~
- 下面的讲解我尝试用一种循序渐进的方式讲述我知道的优先队列,有经验的读者可能会觉得很啰嗦,但我还是觉得这能帮助你梳理一下知识点
优先队列的默认用法—从小到大排序
我们先新建一个优先队列,然后扔四个字符进去,然后用迭代器Iterator或者for-each方式遍历打印,或者直接用println()打印,结果并非从小到大,而是(层序遍历的堆,总之不是你要的~),事实上只有通过优先队列定义的api才能按从小到大取出元素,比如remove方法
此时如果你对:
- 为什么能用for each形式可以打印集合有疑惑:这就要追根溯源到这个PriorityQueue类的来源,Java集合框架是一个大家族,它们由很多的接口定义了不同的功能,再由很多抽象类去逐步实现这些接口的功能,抽象类一代代继承,最后得到如优先队列这样的最终实现类,而for each的遍历方式是它的最上面的祖先Iterable接口中的一个方法,任何实现了Iterable接口的类都能用迭代器进行遍历
- 为什么能System.out.println(XX);直接打印一个XX对象有疑惑:事实上只有实现了toString方法的类,才能在调用这个方法的时候转化成字符串再打印
回到我们的程序
public class PriorityQueueTest {
public static void main(String[] args) {
//这里String类型默认实现Comparable接口的 就是按字典序排序 从小大到
//上面这个注释你可能不太明白,看下去就会明白了~,现在无视它
var pq = new PriorityQueue<String>();
pq.add("B");
pq.add("D");
pq.add("A");
pq.add("C");
//通过迭代器和for each,以及println输出的顺序是(层序遍历的堆)
System.out.println(pq);
for (String s : pq)
System.out.print(s);
System.out.println();
Iterator iter = pq.iterator();
while (iter.hasNext())
System.out.print(iter.next());
System.out.println();
//isEmpty方法是AbstractCollection抽象类中的
while (!pq.isEmpty())
//remove方法按照优先队列中定义的每次返回最小的元素,并删去该值
//本例的最小是字典序最小,但是这个最小的概念是可以通过用户自己定义的
//怎么定义下面会讲
System.out.print(pq.remove());
System.out.println();
System.out.println(pq);
}
}
输出结果
[A, C, B, D]
ACBD
ACBD
//很显然上三种打印的顺序并非我们需要的(打印的是层序的堆),没有实现从小到大排序
ABCD
[]
对String类用优先队列从大到小排序
现在需要补充一个知识点:想要往优先队列里放入一个对象,它就默认会去排序调整它在集合中的位置,与Java集合框架中的其他实现类一样,而一切涉及排序功能的实现类,我们放入集合中的元素都必须实现了Comparable接口,或者在调用构造器时提供了Comparator对象为参数,这句话接下来会用示例讲解~
- 先来看一下String对象的源码,它能直接放入PriorityQueue类是因为它实现了Comparable接口的唯一一个方法compareTo,定义了两个String以何种规则进行比较大小
//这是类的声明部分,可以看到实现了Comparable接口,而这个接口就只有一个compareTo的抽象方法
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence
//抽象方法的实现
public int compareTo(String anotherString) {
byte v1[] = value;
byte v2[] = anotherString.value;
if (coder() == anotherString.coder()) {
return isLatin1() ? StringLatin1.compareTo(v1, v2)
: StringUTF16.compareTo(v1, v2);
}
return isLatin1() ? StringLatin1.compareToUTF16(v1, v2)
: StringUTF16.compareToLatin1(v1, v2);
}
- 现在我们来实现将String类放入PriorityQueue,完成字典序从大到小排序,上面我们讲了,要实现排序可以通过两种方法,对放入PriorityQueue集合的类String实现接口(这是系统的类,final修饰,你想动你不给你机会动呀~,这里我们采用第二种方法,自定义一个Comparator对象传入构造器,你可以理解为第一种方式需要放入的类自带了排序规则,第二种方式是优先队列定义了排序规则,必须有规则才能实现排序)
程序:
public class PriorityQueueTest {
public static void main(String[] args) {
//实例化一个比较器对象
MyComparator myComparator = new MyComparator();
//这里在优先队列的构造方法中传入比较器对象,设定排序规则
var pq = new PriorityQueue<String>(myComparator);
pq.add("B");
pq.add("D");
pq.add("A");
pq.add("C");
System.out.println(pq);
//通过迭代器和for each输出的顺序是元素的层序的堆
for (String s : pq)
System.out.print(s);
System.out.println();
Iterator iter = pq.iterator();
while (iter.hasNext())
System.out.print(iter.next());
System.out.println();
//isEmpty方法是AbstractCollection抽象类中的
while (!pq.isEmpty())
//remove方法按照优先队列中定义的每次返回最小的元素
//但是我们做了点手脚,让大小反转了,Java依旧是输出小的,但是我们重新定义了字典序大的就是小
System.out.print(pq.remove());
System.out.println();
System.out.println(pq);
}
}
//这个自定义的比较器为优先队列设定新的大小规则,
class MyComparator implements Comparator<String> {
//来一下正负反转实现从大到小的优先队列,意思是字典序大的字符串更小
@Override
public int compare(String o1, String o2) {
return -1 * o1.compareTo(o2);
}
}
输出:
[D, C, A, B]
DCAB
DCAB
//分割线,下面就实现了从大到小的打印了,当然Java依旧遵守从小到大打印,只是你改动了其中的规则
DCBA
[]
通过自定义比较器对自定义的类进行从小到大排序
程序:对水果类用优先队列排序,价格低的优先(更小),价格相同字典序小的优先(更小)
public class PriorityQueueTest {
public static void main(String[] args) {
MyComparator myComparator = new MyComparator();
var pq = new PriorityQueue<Fruit>(myComparator);
Fruit fruit1 = new Fruit(10, "Banana");
Fruit fruit2 = new Fruit(10, "Peach");
Fruit fruit3 = new Fruit(20, "Apple");
Fruit fruit4 = new Fruit(30, "Apple");
pq.add(fruit1);
pq.add(fruit2);
pq.add(fruit3);
pq.add(fruit4);
System.out.println(pq);
while (!pq.isEmpty())
System.out.print(pq.remove() + " ");
System.out.println("\n" + pq);
}
}
class Fruit {
private int price;
private String name;
@Override
public String toString() {
return "Fruit{" +
"price=" + price +
", name='" + name + '\'' +
'}';
}
public Fruit(int price, String name) {
this.price = price;
this.name = name;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
class MyComparator implements Comparator<Fruit> {
@Override
public int compare(Fruit o1, Fruit o2) {
//价格相同就定义水果的名称的字典序小的优先级更高(或者说更小)
if (o1.getPrice() == o2.getPrice())
return o1.getName().compareTo(o2.getName());
//价格不同就价格小的优先级更高(更小),这里是>,返回值正数表示这种情况下
// 你定义左侧比右侧优先级更低(更大),而优先队列永远是“小”的先输出
else
return o1.getPrice() > o2.getPrice() ? 1 : -1;
}
}
输出:
[Fruit{price=10, name='Banana'}, Fruit{price=10, name='Peach'}, Fruit{price=20, name='Apple'}, Fruit{price=30, name='Apple'}]
//分割线
Fruit{price=10, name='Banana'} Fruit{price=10, name='Peach'} Fruit{price=20, name='Apple'} Fruit{price=30, name='Apple'}
[]
通过自定义的类实现Comparable接口进行从大到小排序
程序:对水果类用优先队列排序,价格大的优先,价格相同,字典序大的优先
public class PriorityQueueTest {
public static void main(String[] args) {
var pq = new PriorityQueue<Fruit>();
Fruit fruit1 = new Fruit(10, "Banana");
Fruit fruit2 = new Fruit(10, "Peach");
Fruit fruit3 = new Fruit(20, "Apple");
Fruit fruit4 = new Fruit(30, "Apple");
pq.add(fruit1);
pq.add(fruit2);
pq.add(fruit3);
pq.add(fruit4);
System.out.println(pq);
while (!pq.isEmpty())
System.out.print(pq.remove() + " ");
System.out.println("\n" + pq);
}
}
class Fruit implements Comparable<Fruit>{
private int price;
private String name;
@Override
public String toString() {
return "Fruit{" +
"price=" + price +
", name='" + name + '\'' +
'}';
}
public Fruit(int price, String name) {
this.price = price;
this.name = name;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int compareTo(Fruit o) {
if (this.getPrice() == o.getPrice())
return this.getName().compareTo(o.getName()) * -1;
else
return this.getPrice() > o.getPrice() ? -1 : 1;
}
}
输出:
[Fruit{price=30, name='Apple'}, Fruit{price=20, name='Apple'}, Fruit{price=10, name='Peach'}, Fruit{price=10, name='Banana'}]
//分割线
Fruit{price=30, name='Apple'} Fruit{price=20, name='Apple'} Fruit{price=10, name='Peach'} Fruit{price=10, name='Banana'}
[]
用lambda表达式优化比较器的使用
补充一个知识点吧:对于那些只带有一个抽象方法的接口,又被称之为函数式接口,所有能用函数式接口对象的地方,都能用lambda表达式代替(写起来快一点,有时还能解耦合?)
举个上面的栗子,Comparator接口就是一个函数式接口,下面是它的接口的声明,@后面的写的很清楚了,告诉你它是一个函数式接口~,所以偶尔看看这些类的实现对我们学习Java会有很大帮助
@FunctionalInterface
public interface Comparator<T>
下面用lambda表达式对上面那个,通过构造Comparator比较器对象,实现水果按价格和字典序从小到大排序例子进行优化
程序:
public class PriorityQueueTest {
public static void main(String[] args) {
//通过lambda表达式创建比较器接口对象
Comparator<Fruit> comparator = (o1, o2) -> {
//价格相同就定义水果的名称的字典序小的优先级更高(或者说更小)
if (o1.getPrice() == o2.getPrice())
return o1.getName().compareTo(o2.getName());
//价格不同就价格小的优先级更高(更小),这里是>,返回值正数表示这种情况下
// 你定义左侧比右侧优先级更低(更大),而优先队列永远是“小”的先输出
else
return o1.getPrice() > o2.getPrice() ? 1 : -1;
};
//这里和之前的比较器用法相同,函数式接口完美兼容lambda表达式
var pq = new PriorityQueue<Fruit>(comparator);
Fruit fruit3 = new Fruit(20, "Apple");
Fruit fruit4 = new Fruit(30, "Apple");
Fruit fruit1 = new Fruit(10, "Banana");
Fruit fruit2 = new Fruit(10, "Peach");
pq.add(fruit1);
pq.add(fruit2);
pq.add(fruit3);
pq.add(fruit4);
System.out.println(pq);
while (!pq.isEmpty())
System.out.print(pq.remove() + " ");
System.out.println("\n" + pq);
}
}
class Fruit {
private int price;
private String name;
@Override
public String toString() {
return "Fruit{" +
"price=" + price +
", name='" + name + '\'' +
'}';
}
public Fruit(int price, String name) {
this.price = price;
this.name = name;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
输出:
[Fruit{price=10, name='Banana'}, Fruit{price=10, name='Peach'}, Fruit{price=20, name='Apple'}, Fruit{price=30, name='Apple'}]
//分割线
Fruit{price=10, name='Banana'} Fruit{price=10, name='Peach'} Fruit{price=20, name='Apple'} Fruit{price=30, name='Apple'}
[]