Java 1.8 Priority Queue 代码分析

image-20200319105209368 image-20200323010707745

在实际生活中,队列都是有优先级的,在某些条件下不一定按照先到先得,而是按照元素的某些特性进行出队的。

  • 比如游戏中 小兵的攻击并不固定,而是攻击离它最近的单位,或者是攻击血量最小的单位。
  • 在医院排序看病,医生也会根据患者的患病程度进行就诊,先救治特别紧急的患者。

# 为什么需要优先队列?

按照优先队列的性质,每次出队取最符合“条件”的元素。

那其实也不一定需要优先队列,我用数组,或者链条其实也能实现,只不过我在添加元素的时候对元素进行排序就可以了。这样不是也能解决问题吗?

时间复杂度对比:

  • 普通线性结构:入队 O(1) 出队 O(n)

  • 顺序线性结构:入队 O(n) 出队 O(1)

  • 堆:入队O(logn) 出队 O(logn)

优先队列可以解决什么问题?

  • 在 M 个元素中,找出前 K 个元素

# Java 1.8 的底层采用最小[堆](./数据结构 - 二叉堆.md)进行实现。

  • 比较器

    PriorityQueue 构造函数中允许传入比较器用于组装堆。在初始化时便可以传入比较器。

    PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);
    q.add(1);
    q.add(2);
    q.add(3);
    
    Integer result = q.peek();
    System.out.println(result); // 3
    
  • 添加元素

    优先队列中添加元素实际上是在堆中添加元素时间复杂度为 (logn).

    // 添加指定的元素到优先队里中
    public boolean add(E e) {
        return offer(e);
    }
    
    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;
    }
    

    添加元素时,首先判断当前容器是否还能承载新元素,如果不能则进行扩容操作 grow

    如果当前堆中不还没有元素则直接添加即可,否则进行 Sift Up (上浮) 操作。

    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }
    

    实际就是进行上浮,与父节点进行对比,迭代交换

  • 取出 “最符合条件”的元素

    添加元素的时候,其实就是已经形成了最符合条件的堆(最大堆|最小堆),根节点其实就是将要取出的节点,后续我们只需要进行 堆的下浮(Sift Down)即可。

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }
    
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }
    
最后编辑时间: 7/8/2020, 3:00:50 PM