priorityQuene

优先队列，意思是呢，它能对add进去的元素排列

可以给它一个Comparator指定排列顺序

默认是最小堆

常用的有peek();poll();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

PriorityQueue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            q.add(4);
            q.add(33);
            q.add(14);
            q.add(100);
            System.out.println(q.toString());//[4, 33, 14, 100]
            System.out.println(q.peek());//4
            Comparator<? super Integer> cp = q.comparator();

            Object[] list=q.toArray();

            System.out.println(Arrays.toString(list));//[4, 33, 14, 100]

这是最简单的情况

当然最让我们头疼的是这个⽐较器，拿这个例⼦来说为什么传⼊o1-o2它就是最⼩堆了？ 在添加元素时，会使⽤offer(E e)函数加⼊e到堆⾥

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public boolean offer(E e) {
	if (e == null)
		throw new NullPointerException();
	modCount++;
	int i = size;
	if (i >= queue.length)
	grow(i + 1);
	siftUp(i, e);
	size = i + 1;
	return true;
}

可以看到有⼀个siftUp(),它⼜是什么呢？

1
2
3
4
5
6

private void siftUp(int k, E x) {
	if (comparator != null)
		siftUpUsingComparator(k, x, queue, comparator);
	else
		siftUpComparable(k, x, queue);
}

哦，原来是是⽤Comparator的siftUp()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

private static <T> void siftUpUsingComparator(
	int k, T x, Object[] es, Comparator<? super T> cmp) {
	while (k > 0) {
		int parent = (k - 1) >>> 1;
		Object e = es[parent];
		if (cmp.compare(x, (T) e) >= 0)
			break;
		es[k] = e;
		k = parent;
	}
	es[k] = x;
}

x是被添加的元素，es是这个queue， 如果cmp.compare(x, (T) e) <0,这⾥假设我们传⼊⼀个很⼩的数（按理说要添加到最⼩堆堆顶），每次x ⼩于e,⽐较器返回⼩于0，这⾥两⾏代码(es[k] = e;k = parent;)相当于元素向堆顶⾛，直到到达堆顶 break退出while。我们成功把这个元素放到堆顶。如果我们让**⽐较器返回⼤于0**呢，那么，那么不会向 堆顶⾛，这就是最⼤堆了，怎么让⽐较器返回⼤于0呢？(o1,o2)->o2-o1就⾏了，插⼊的x很⼩， cmp.compare(x,e)每次都返回正数(e-x>0),⾃然这个x不会向堆顶移动。

优先队列里也可以放其他的对象，比如int[]

指定按照int[]的第一个从小到大排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

 PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int []>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
//也可以用lambda表达式：(o1,o2) o1[0]-o2[0];
            q.add(new int[]{4,19});
            q.add(new int[]{33,20});
            q.add(new int[]{14,22});
            q.add(new int[]{100,23});

            int []nn=q.poll();
            System.out.println(Arrays.toString(nn));//[4, 19]
            nn=q.poll();
            System.out.println(Arrays.toString(nn));//[14, 22]
            nn=q.poll();
            System.out.println(Arrays.toString(nn));//[33, 20]
            nn=q.poll();
            System.out.println(Arrays.toString(nn));//[100, 23]

ref:

PriorityQueue的API文档说明：

构造方法摘要
**PriorityQueue**() 使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。
**PriorityQueue**(Collection<? extends E> c) 创建包含指定 collection 中元素的 PriorityQueue。
**PriorityQueue**(int initialCapacity) 使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。
**PriorityQueue**(int initialCapacity, Comparator<? super E> comparator) 使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。
**PriorityQueue**(PriorityQueue<? extends E> c) 创建包含指定优先级队列元素的 PriorityQueue。
**PriorityQueue**(SortedSet<? extends E> c) 创建包含指定有序 set 元素的 PriorityQueue。
方法摘要
boolean **add**(E e) 将指定的元素插入此优先级队列。
void **clear**() 从此优先级队列中移除所有元素。
Comparator<? super E> **comparator**() 返回用来对此队列中的元素进行排序的比较器；如果此队列根据其元素的自然顺序进行排序，则返回 null。
boolean **contains**(Object o) 如果此队列包含指定的元素，则返回 true。
Iterator<E> **iterator**() 返回在此队列中的元素上进行迭代的迭代器。
boolean **offer**(E e) 将指定的元素插入此优先级队列。
E **peek**() 获取但不移除此队列的头；如果此队列为空，则返回 null。
E **poll**() 获取并移除此队列的头，如果此队列为空，则返回 null。
boolean **remove**(Object o) 从此队列中移除指定元素的单个实例（如果存在）。
int **size**() 返回此 collection 中的元素数。
Object[] **toArray**() 返回一个包含此队列所有元素的数组。
<T> T[] **toArray**(T[] a) 返回一个包含此队列所有元素的数组；返回数组的运行时类型是指定数组的类型。
从类 java.util.AbstractQueue 继承的方法
addAll, element, remove
从类 java.util.AbstractCollection 继承的方法
containsAll, isEmpty, removeAll, retainAll, toString
从类 java.lang.Object 继承的方法
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
从接口 java.util.Collection 继承的方法
containsAll, equals, hashCode, isEmpty, removeAll, retainAll