コレクション - PriorityQueueソースコード解析

2022-02-19 05:12:14

JDKバージョン

JDK 1.8.0_110

参考文献

Java PriorityQueueの徹底理解ソースコードを組み合わせてPriorityQueueを解説する Java PriorityQueueの深い理解 - CarpenterLee - Blogland

概要

の前に、Javaの ArrayDeque を説明するための例として スタック と キュー という特別な種類のキューがあります。 プライオリティキュー というのは、優先キューです。 優先キューの目的は、各要素がキューの中で最も低い重みで取り出されるようにすることである (Javaの優先キューは一度に最小の要素を取り、C++の優先キューは一度に最大の要素を取ります)。ここには大きさの関係があり 要素の大きさは、要素そのものの自然な並び方で判断できる( 自然順序 )、あるいは構築時に渡されるコンパレータによって行われます。 ( コンパレータ C++のアフィン関数に似ている）。

Javaでは プライオリティキュー を実装しています。 キュー インタフェースは、null 要素を配置することを許しません。ヒープ、特に完全なバイナリツリー ( 完全なバイナリツリー ) によって実装されています。 スモールトップヒープ (非リーフノードの重みは、その左右の子の重みよりも大きくない)つまり、配列を プライオリティキュー の基礎となる実装は

上の図では、各要素に階層的に番号を振っていますが、よく見ると、親ノードと子ノードが関連しており、より具体的には親ノードと子ノードが次のように関連していることが分かります。

左No = 親No*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2

上記の3つの式で、ノードの親と子ノードの添え字を簡単に計算することができます。このため、ヒープを直接配列に格納することが可能です。

プライオリティキュー peek() と element 操作は定数時間、add(), offer(), パラメータなしの remove(), poll() メソッドはいずれも時間複雑度 0.5 である。 log(N) .

メソッドプロファイリング

add() と offer()

add(E e) と offer(E e) のセマンティクスは同じで、どちらも優先キューに要素を挿入します。ただし、Queue インターフェースでは、挿入に失敗したときに前者は例外をスローし、後者は false を返すという異なる処理を行うことが指定されています。については PriorityQueue この2つのメソッドに違いはありません。

新しく追加された要素は、小さなトップスタックの性質を壊す可能性があるので、必要な調整を行う必要があります。

//offer(E e)
public boolean offer(E e) {
    if (e == null)//Null elements are not allowed
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);//automatically expand the capacity
    size = i + 1;
    if (i == 0)//queue was empty, this is the first element inserted
        queue[0] = e;
    else
        siftUp(i, e);//adjust
    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)// call the comparator's compare method
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

新しく追加された要素xは、小さなトップヒープの性質を壊す可能性があるので、調整が必要である。調整処理は ** である。kで指定された位置から、x >= queue[parent]** が満たされるまで、xを現在の地点の親と比較し、層ごとに入れ替える。ここでの比較は、要素の自然な順序であってもよいし、コンパレータの順序に依存してもよいことに注意してください。

element() と peek()

element() と peek() のセマンティクスは同じで、どちらもキューの中で最も重みの小さい要素であるトップエレメントを取得しますが削除しません。唯一の違いは、前者はメソッドが失敗すると例外をスローし、後者はヌルを返すことです。ヒープが配列で表現されているため、添え字の関係から、0 番目の添え字にある要素が先頭の要素になります。ですから を直接返す配列です。 0 要素を添え字 .

また、コードも非常にきれいです。

//peek()
public E peek() {
    if (size == 0)
        return null;
    return (E) queue[0];//the element at the 0 subscript is the smallest one
}

remove()とpoll()

remove() と poll() のセマンティクスも、キューの最初の要素を取得して削除するという点では同じですが、前者はメソッドに失敗すると例外をスローし、後者は null を返すという違いがあります。delete 操作はキューの構造を変更するので、小さなトップヒープの性質を維持するために必要な調整を行う必要があります。

コードは以下の通りです。

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];//the element at the 0 subscript is the smallest one
    E x = (E) queue[s];
    queue[s] = null;
    if (s ! = 0)
        siftDown(0, x);//adjust
    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) {
    	// first find the smaller of the left and right children, record it in c, and use child to record its subscript
        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;//then replace the original value with c
        k = child;
    }
    queue[k] = x;
}

remove(オブジェクト o)

remove(Object o) メソッドは、キュー内の o と等しい要素を削除するために使用されます（複数の等しい要素がある場合は、1 つだけが削除されます）; それは キュー インターフェイスの中にあるメソッドです。 コレクション インターフェイスを使用します。また、削除される要素の位置は任意であるため、他の関数に比べて調整作業が若干面倒である。具体的には、remove(Object o)は2つのケースに分けられる。

最後の要素が削除される。調整なしの直接削除。
最後尾でない要素を削除します。最後の要素を参照して、削除箇所から一度だけ siftDown() を呼び出す。ここでは繰り返さない。

具体的なコードは以下の通りです。

//remove(Object o)
public boolean remove(Object o) {
	//find the subscript of the first element that satisfies o.equals(queue[i]) by traversing the array
    int i = indexOf(o);
    if (i == -1)
        return false;
    int s = --size;
    if (s == i) //case 1
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);//case 2
        ......
    }
    return true;
}