认识达内从这里开始

一、结构

昆明IT培训的老师发现PriorityQueue是一个堆,任意节点都是以它为根节点的子树中的最小节点

堆的逻辑结构是完全二叉树状的，存储结构是用数组去存储的，随机访问性好。最小堆的根元素是最小的，最大堆的根元素是最大的

这是一个最小堆的逻辑结构

这是他的存储结构，是用数组来存储的。

可以看到，i下标的数组元素，他的父节点是(i-1)/2，他的左右节点分别是i*2+1,i*2+2

二、容量

2.1初始容量11

2.2扩展容量

1

2

3

4

5

6

7

8

9

private void grow(int minCapacity) {

    int oldCapacity = queue.length;

    // Double size if small; else grow by 50%

    int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));

    // overflow-conscious code

    if (newCapacity - MAX_ARRAY_SIZE > 0)

        newCapacity = hugeCapacity(minCapacity);

    queue = Arrays.copyOf(queue, ewCapacity);

}

当容量不足的时候，会调用此方法，如果当前容量较小（小于64），则将容量增大一倍+2,如果当前容量较大，则容量增大一半

三、插入

插入元素会调用siftUp方法。

1

2

3

4

5

6

7

8

9

10

11

12

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;

}

当优先队列不指定比较器的时候，插入元素，会调用siftUpComparable

k表示元素将要插入的位置

这个方法的意思是，在以k为子节点的子树插入元素x，并保持该子树的顺序。（把k看作这个子树的叶子节点）

step1:得出父元素的下标

strp2:计算出要插入元素的位置k。如果插入元素大于父元素，将父元素移动到k的位置，k移动到其父元素，并从第一步开始循环执行

step3:在k的位置插入元素

四、删除

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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;

}

删除会调用这个方法。删除都是将队尾的元素替换掉删除掉的位置

k表示元素将要插入的位置

这个方法的意思是，在k的子树插入元素x，并保持k位置子树的顺序（x是其子树的最小节点）。（把k看作这个子树的根节点）

这里要注意，像这种二叉树结构，下标大于size<<2都是叶子节点，其他的节点都有子节点。所以注意到循环条件，如果k是叶子节点的下标，则直接替换，因为其已经没有子树了，那么肯定是以其为根节点的最小元素

step1:算出k的左右节点的下标

step2:如果k大于左右节点中的最小一个，则k与最小的节点互换位置，并循环step1

step3:在k位置赋值x