在使用java的优先队列PriorityQueue的时候,会看到这样的用法。 PriorityQueueInteger queue = new PriorityQueueInteger(new ComparatorInteger(){ @Override public int compare(Integer o1, Integer o2){ return o1.compareTo(o2); }
在使用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);
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持易盾网络。