Java内置的优先队列PriorityQueue

PriorityQueue是Java内置的优先队列,每次取出来的元素是最小的。PriorityQueue可以做到自动扩容。PriorityQueue中的对象必须是可比较的。

 

例如,最简单的情况,在PriorityQueue中保存整数:

PriorityQueue<Integer> priInt = new PriorityQueue<>();

然后在其中依次添加五个整数(注意,在PriorityQueue中添加对象,可以调用add,也可以调用offer。)

priInt.add(1);
priInt.add(3);
priInt.add(4);
priInt.add(5);
priInt.add(2);

然后通过poll函数所取出来的值就是从小到大排列好的1,2,3,4,5

 

int n = priInt.poll(); // n is 1
n = priInt.poll(); // n is 2
n = priInt.poll(); // n is 3
n = priInt.poll(); // n is 4
n = priInt.poll(); // n is 5

PriorityQueue中还可以放置自定义对象。由于PriorityQueue中的对象必须是可比较的,所以必须为自定义对象定义比较规则。

例如,对于自定义类

class MyClass {
    int n1;
    int n2;
        
    public MyClass(int n1, int n2) {
        this.n1 = n1;
        this.n2 = n2;
    }
}

 

具体做法有3种

1、MyClass实现接口Comparable,在override的函数compareTo中定义比较规则

static class MyClass implements Comparable<MyClass> {
    int n1;
    int n2;
    
    public MyClass(int n1, int n2) {
        this.n1 = n1;
        this.n2 = n2;
    }

    @Override
    public int compareTo(MyClass o) {
        return this.n2 - o.n2;
    }
}

然后,PriorityQueue上就不用做任何额外的操作了,直接定义即可

PriorityQueue<MyClass> priMyClass = new PriorityQueue<>();

2、在PriorityQueue的参数中,通过Comparator接口定义比较规则

PriorityQueue<MyClass> priMyClass = new PriorityQueue<>(
    new Comparator<MyClass>() {
        public int compare(MyClass o1, MyClass o2) {
            return o1.n2 - o2.n2;
        }
    }
);

3、在PriorityQueue的参数中,通过lambda表达式定义比较规则。写起来最省事

PriorityQueue<MyClass> priMyClass = new PriorityQueue<>((MyClass o1, MyClass o2) -> o1.n2 - o2.n2);

 

上一篇:js基石之---es7的decorator修饰器


下一篇:034.Python的__str__,__repr__,__bool__ ,__add__和__len__魔术方法