java集合（2）——优先队列的comparator_java优先队列的compator

1. 优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。
2. 优先队列要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。
3. PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。

##源码查看
1.首先先看add

  public boolean add(E e) {
        return offer(e);
    }
1
2
3

2.进入offer

 public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.查看siftup

 private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
1
2
3
4
5
6

4.查看siftUpUsingComparator(k, x)

  private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
1
2
3
4
5
6
7
8
9
10
11

在上一个方法中，k是最后一个元素的索引，所以e代表最后一个元素，x代表插入元素。所以在重写的比较器comparator（o1,o2）中,o1代表要插入的元素，o2代表最后一个元素。所以o1-o2是小根堆，o2-o1是大根堆。

private static PriorityQueue<Person> pq = new PriorityQueue<Person>(new Comparator<Person>() {

		

		public int compare(Person o1, Person o2) {
			// TODO Auto-generated method stub
			
			return o1.getId()-o2.getId();
		}
		
	});

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