深入了解Java PriorityQueue

PriorityQueue

本文github地址

Java中PriorityQueue通过二叉小顶堆实现,可以为此相同株完全二叉树表示。本文自Queue接口函数出发,结合生动的图解,深入浅出地解析PriorityQueue每个操作的切切实实经过以及时空复杂度,将让读者建立对PriorityQueue建立清晰而尖锐之认识。

圆介绍

前面以Java
ArrayDeque啊条例讲解了StackQueue,其实还有一样种独特之队叫做PriorityQueue,即先队列。事先队列的来意是会担保每次取出的因素都是排中权值最小的(Java的预队列每次取最好小元素,C++的事先队列每次取最好特别因素)。这里牵涉到了大小关系,素大小的评议好经过元素本身的当然顺序(natural
ordering
),也足以通过组织时传出的比较器
Comparator,类似于C++的仿函数)。

Java中PriorityQueue实现了Queue接口,不允放入null素;其通过堆实现,具体说是通过一点一滴二叉树(complete
binary
tree
)实现的小顶堆(任意一个非叶子节点的权值,都无超出其左右子节点的权值),也即代表可以经数组来作PriorityQueue的底色实现。

C++ 1

达图被我们吃每个元素以层序遍历的点子进行了号码,如果您足够细心,会意识父节点和子节点的编号是起关联的,更确切的说父子节点的编号之间发生如下事关:

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

由此上述三个公式,可以随心所欲计算出某节点的父节点以及子节点的下标。这也即是怎可以一直用数组来囤堆的故。

PriorityQueuepeek()element操作是常数时间,add(), offer(),
无参数的remove()以及poll()法的流年复杂度都是log(N)

计分析

add()和offer()

add(E e)offer(E e)的语义相同,都是朝优先队列中插入元素,只是Queue接口规定二者对插入失败时之拍卖不同,前者以插入失败时抛来异常,后虽然则会回到false。对于PriorityQueue这片单道其实没什么差别。

C++ 2

乍进入的元素或会见毁掉小顶堆的习性,因此用展开必要之调动。

//offer(E e)
public boolean offer(E e) {
    if (e == null)//不允许放入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()类似于ArrayList里的grow()函数,就是重新申请一个更不行的一再组,并拿原本数组的素复制过去,这里不再赘述。需要小心的是siftUp(int k, E x)办法,该办法用于插入元素x连保持堆的特色。

//siftUp()
private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

新入的因素x恐会见破坏小顶堆的特性,因此要开展调。调整之过程吧:k点名的职上马,将x逐层与目前触及的parent开展较并交换,直到满足x >= queue[parent]为止。注意这里的于可是因素的自顺序,也可是赖比较器的逐条。

element()和peek()

element()peek()的语义完全相同,都是收获但非删除队首元素,也就是排中权值最小的雅元素,二者唯一的分是当方法失败时前者抛来老,后者返回null。根据小顶堆的性,堆顶那个元素即是全局最小之充分;由于堆用数组表示,根据下标关系,0下标处的不行元素既是积顶元素。所以一直回数组0下标处的好元素即可

C++ 3

代码也就是死简单:

//peek()
public E peek() {
    if (size == 0)
        return null;
    return (E) queue[0];//0下标处的那个元素就是最小的那个
}

remove()和poll()

remove()poll()办法的语义也完全相同,都是收获并删除队首元素,区别是当方法失败时前者抛来怪,后者返回null。由于删除操作会改变队列的布局,为保护小顶堆的性,需要进行必要之调。

C++ 4
代码如下:

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];//0下标处的那个元素就是最小的那个
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);//调整
    return result;
}

上述代码首先记录0下标处的要素,并因此最后一个素交替0下标位置的要素,之后调用siftDown()方式对堆放进行调,最后回到原0下标处的慌元素(也就算是无与伦比小之非常元素)。重点是siftDown(int k, E x)方法,该方法的意是k点名的职务上马,将x逐层向下及当下触及的横孩子遭受比小之好交换,直到x低于或顶左右儿女负的别一个得了

//siftDown()
private void siftDown(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        //首先找到左右孩子中较小的那个,记录到c里,并用child记录其下标
        int child = (k << 1) + 1;//leftNo = parentNo*2+1
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;//然后用c取代原来的值
        k = child;
    }
    queue[k] = x;
}

remove(Object o)

remove(Object o)方式用于去队列中以及o顶的某部一个素(如果发多单相当,只去一个),该方法无是Queue接口内之办法,而是Collection接口的道。由于删除操作会改变队列结构,所以要开展调;又由删除元素的位置或是随机的,所以调整过程较其他函数稍加繁琐。具体来说,remove(Object o)得分开呢2种状态:1.
抹的是最终一个素。直接删除即可,不需调。2.
去除的匪是最终一个要素,从删除点开始盖最后一个素也参照调用一糟siftDown()即可。此处不再赘述。

C++ 5

实际代码如下:

//remove(Object o)
public boolean remove(Object o) {
    //通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
    int i = indexOf(o);
    if (i == -1)
        return false;
    int s = --size;
    if (s == i) //情况1
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);//情况2
        ......
    }
    return true;
}