java - PriorityQueue の remove メソッドはヒープを再配置しますか?

Question

removeメソッドが Java のオブジェクトで呼び出されると、PriorityQueueヒープの先頭が削除されます。新しい最小要素を先頭に配置するために、残りのヒープで並べ替え操作が行われていますか? たとえば、 がcompareTo呼び出されたときにメソッドremoveが呼び出されますか?

これがドキュメントにある場合は申し訳ありませんが、どこにも見つかりません。前もって感謝します。

Answer 1

場合によります。removeを裏打ちする配列の最後の要素を ing している場合、再ソートPriorityQueueは行われません。remove他の要素がある場合は、その要素 (siftUpおよびsiftDown)を並べ替えます。

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

private E removeAt(int i) {
    assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}