定义优先级队列,实现了AbstractQueue
优先队列跟普通的队列不一样,普通队列是一种遵循FIFO规则的队列,拿数据的时候按照加入队列的顺序拿取。 而优先队列无论插入的顺序如何每次拿数据的时候都会拿出优先级最高(优先级value最小)的数据。
Priority原理分析
优先队列内部维护着一个堆,每次取数据的时候都从堆顶拿数据,这就是优先队列的原理。
每次add的时候都会siftUp(i, e);从下往上调整,因为新增元素是加到最后一个叶子节点
每次poll的时候都会siftDown(0, x); 从上往下调整,因为删除元素是删除堆顶的元素
例子:
Comparatortest = new Comparator() {
@Override
public int compare(Integer t1, Integer t2) { return t1 - t2;} };
PriorityQueue test2 = new PriorityQueue(6, test);
test2.add(6);
test2.add(10);
test2.add(2);
test2.add(3);
test2.add(4);
test2.add(5);
System.out.println(test2.toString());
System.out.println(test2.remove());
输出:
[10, 6, 5, 3, 4, 2]
2