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

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

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

PriorityQueue queue = new PriorityQueue(new Comparator(){

@Override

public int compare(Integer o1, Integer o2){

return o1.compareTo(o2);

}

});

那这样到底构造的是最大优先还是最小优先队http://列呢？

看看源码

看看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 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) < 0http://，则执行元素往上走的方法。

注：在siftUp中，如果是最小堆，那么应该是较小的元素往上走，如果是最大堆，则应该是较大的元素往上走。

由于源码中新入队元素x是在第1个参数的位置，因此最大/最小优先队列主要根据第1个参数的大小关系来判断。

//对于最大堆，当x>e时，让x上升，则 x>e时返回负数，即

int compare(Integer FGOYSx, Integer e){

return x > e ? -1 : 1;

}

//对于最小堆，当x

int compare(Integer x, Integer e){

return x < e ? -1 : 1; // return x.compareTo(e);

}

结论：

// 最小优先队列，直接 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);

int compare(Integer x, Integer e){

return x < e ? -1 : 1; // return x.compareTo(e);

}

结论：

// 最小优先队列，直接 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);

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。