PriorityQueue 源码

发表于

PriorityQueue

1
2
3
4
5
6
7
8
9
arduino复制代码public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

上浮图片

siftup.png

offer 向堆中添加元素 向上比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ini复制代码public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    // 扩容
    if (i >= queue.length)
        grow(i + 1);
    // 数量+1
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
    // 下标的位置i e 
        siftUp(i, e);
    return true;
}

siftUp 向上比较

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

siftUpComparable 构建最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ini复制代码private void siftUpComparable(int k, E x) 
{
    // 梳理逻辑 每次加入一个元素 都要向上比较 然后 重新构建一个最小堆
    Comparable<? super E> key = (Comparable<? super E>) x;
    // k=0 的时候到达了根节点
    while (k > 0) 
    {
        int parent = (k - 1) >>> 1;
        // 父元素的值
        Object e = queue[parent];
        // 当添加的值比父元素大的时候 退出循环  
        if (key.compareTo((E) e) >= 0)
            //添加的值
            break;
        // 当添加的值比父元素小的时候  把父元素的值对调到传入值的位置
        // 
        queue[k] = e;
        k = parent;
    }
    // 传入的x 最终放的位置
    queue[k] = key;
}

poll 取出队列中的队首数据 删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
scss复制代码public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    // 1、取到队列中的第一个元素
    E result = (E) queue[0];
    // 2、取到最后一个元素
    E x = (E) queue[s];
    //3、GC 清空数据
    queue[s] = null
    // 4、往下比较
    if (s != 0)
        siftDown(0, x);
        // 返回队首元素
    return result;
}

siftDown 下沉 k=0 | x 最后一个元素

1
2
3
4
5
6
scss复制代码private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

siftDownComparable(k, x); k=0 | x 最后一个元素 就是从第一个元素开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ini复制代码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) 
    {
        // 1、左孩子节点index  默认左节点最小值
        int child = (k << 1) + 1; 
        // 2、左孩子节点值
        Object c = queue[child];
        // 3、右孩子节点值
        int right = child + 1;
        // 比较左右节点的最大值 取到最小值index
        if (right < size &&
            // 如果左边>右边  表示右节点是最小值节点 不是默认的左节点
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            // 
            c = queue[child = right];
        // 再次比较根节点的值 也就是传入的x 和孩子节点中的最小值做比较  如果小于的话 退出循环 
        // 已经是最小堆了
        if (key.compareTo((E) c) <= 0)
            break;
        // 也就是父节点的值比孩子节点中的最小值要大 不符合最小堆 继续调整
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

下沉图片

siftdown.png

heapify 将一个无序数组构造成最小堆

1
2
3
4
5
6
7
8
9
arduino复制代码private void heapify() 
{
    /**int i = (size >>> 1) - 1，
      这行代码是为了找寻最后一个非叶子节点，然后倒序进行"下移"siftDown操作
     */
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        // i 数组下标 queue[i] 要下沉的值
        siftDown(i, (E) queue[i]);
}

heapify图形结合

图片.png

图片.png

图片.png

图片.png
我们观察下用数组a建成的二叉堆，很明显，对于叶子节点4、15、11、1、3来说，它们已经是一个合法的堆。所以只要最后一个节点的父节点，也就是最后一个非叶子节点a[4]=10开始调整，然后依次调整a[3]=12，a[2]=5，a[1]=6，a[0]=7，分别对这几个节点做一次”下移”操作就可以完成了堆的构造。ok，我们还是用图解来分析下这个过程。

假设有一个无序的数组，要求我们将这个数组建成一个二叉堆，你会怎么做呢？最简单的办法当然是将数组的数据一个个取出来，调用入队方法。但是这样做，每次入队都有可能会伴随着元素的移动，这么做是十分低效的。那么有没有更加高效的方法呢，我们来看下。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%