Does PriorityQueue's remove method rearrange the heap?

Question

When the remove method is called on a PriorityQueue object in java, the head of the heap is removed. To put the new minimum element at the head, are any sorting operations done on the rest of the heap? For example, is the compareTo method called when remove is called?

Apologies if this is in the docs, I can't find it anywhere. Thanks in advance.

Answer 1

The PriorityQueue is implemented as a balanced binary heap implemented as an array. When an element is removed, the heap has to reorder itself to keep the order of the heap.

The proof is in the comments

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
private transient Object[] queue;

Also in the class javadoc

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

For remove(), for example, you remove the root of the Heap. You take the last element, ie. right-most leaf at the last level of the binary tree, and put it as root and make sift down until it finds its place (based on Comparator). That takes at worst O(log n) time.

Answer 2

It depends. If you are removeing the last element in the array that backs the PriorityQueue, then no resorting will be done. If you remove any other element, it will reorder its elements (siftUp and 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;
}