Heap(Priority Queue) in Java Java实现的堆(优先队列)

Heap in Java

For definition of heap or priority queue, please refer to Heap.

Heap is implemented in java.util. The class is named as PriorityQueue supposedly for application purposes.

/**
 * An unbounded priority {@linkplain Queue queue} based on a priority heap.
 * The elements of the priority queue are ordered according to their
 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
 * provided at queue construction time, depending on which constructor is
 * used.  A priority queue does not permit {@code null} elements.
 * A priority queue relying on natural ordering also does not permit
 * insertion of non-comparable objects (doing so may result in
 * {@code ClassCastException}).
 *
 * <p>The <em>head</em> of this queue is the <em>least</em> element
 * with respect to the specified ordering.  If multiple elements are
 * tied for least value, the head is one of those elements -- ties are
 * broken arbitrarily.  The queue retrieval operations {@code poll},
 * {@code remove}, {@code peek}, and {@code element} access the
 * element at the head of the queue.
 *
 * <p>A priority queue is unbounded, but has an internal
 * <i>capacity</i> governing the size of an array used to store the
 * elements on the queue.  It is always at least as large as the queue
 * size.  As elements are added to a priority queue, its capacity
 * grows automatically.  The details of the growth policy are not
 * specified.
 *
 * <p>This class and its iterator implement all of the
 * <em>optional</em> methods of the {@link Collection} and {@link
 * Iterator} interfaces.  The Iterator provided in method {@link
 * #iterator()} and the Spliterator provided in method {@link #spliterator()}
 * are <em>not</em> guaranteed to traverse the elements of
 * the priority queue in any particular order. If you need ordered
 * traversal, consider using {@code Arrays.sort(pq.toArray())}.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * Multiple threads should not access a {@code PriorityQueue}
 * instance concurrently if any of the threads modifies the queue.
 * Instead, use the thread-safe {@link
 * java.util.concurrent.PriorityBlockingQueue} class.
 *
 * <p>Implementation note: this implementation provides
 * O(log(n)) time for the enqueuing and dequeuing methods
 * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
 * linear time for the {@code remove(Object)} and {@code contains(Object)}
 * methods; and constant time for the retrieval methods
 * ({@code peek}, {@code element}, and {@code size}).
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 * Java Collections Framework</a>.
 *
 * @since 1.5
 * @author Josh Bloch, Doug Lea
 * @param <E> the type of elements held in this queue
 */
@SuppressWarnings("unchecked")
public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

The Java code blocks in this article are from jdk-17.

1 Core Methods

Java’s Priority Queue use template to store instances of any class. The Priority Queue is implemented with min heap, meaning the top of the heap stores the element with the least value or priority.

1.1 Object Storage

Objects are stored in an array:

/**
 * 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.
 */
transient Object[] queue; // non-private to simplify nested class access

Elements will be stored in this array. When the array is full, grow() is called to expand the array:

/**
 * Increases the capacity of the array.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            minCapacity - oldCapacity, /* minimum growth */
            oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                                        /* preferred growth */);
    queue = Arrays.copyOf(queue, newCapacity);
}

newCapacity is calculated in an overflow-safe way. If JVM has enough space, preferred length will be returned; otherwise minimum growth will be returned. OutOfMemoryError will be thrown only if there’s not enough space even for the minimum growth.

1.2 siftUp

Because PriorityQueue supports customized comparing method, siftUp() is implemented as such:

/**
 * Inserts item x at position k, maintaining heap invariant by
 * promoting x up the tree until it is greater than or equal to
 * its parent, or is the root.
 *
 * To simplify and speed up coercions and comparisons, the
 * Comparable and Comparator versions are separated into different
 * methods that are otherwise identical. (Similarly for siftDown.)
 *
 * @param k the position to fill
 * @param x the item to insert
 */
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        siftUpComparable(k, x, queue);
}

1.2.1 siftUpComparable

This method is implemented exactly as mentioned in Heap. >>> operator is used for better performance.

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

1.2.2 siftUpUsingComparator

The only difference is the comparing line. Other lines are identical as those in siftUpComparable().

private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = x;
}

1.3 siftDown

Like siftUp(), siftDown() supports customized comparator as well.

/**
 * Inserts item x at position k, maintaining heap invariant by
 * demoting x down the tree repeatedly until it is less than or
 * equal to its children or is a leaf.
 *
 * @param k the position to fill
 * @param x the item to insert
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x, queue, size, comparator);
    else
        siftDownComparable(k, x, queue, size);
}

Let’s only take a look at siftDownComparable():

private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
    // assert n > 0;
    Comparable<? super T> key = (Comparable<? super T>)x;
    int half = n >>> 1;           // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = es[child];
        int right = child + 1;
        if (right < n &&
            ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
            c = es[child = right];
        if (key.compareTo((T) c) <= 0)
            break;
        es[k] = c;
        k = child;
    }
    es[k] = key;
}

Each iteration first assume the left child is least, and then compare it to the right child. If the right child is less, assign it to the local variable c(the least child element) and child(the least child index).

1.4 heapify

This method is implemented as mentioned in Heap as well:

/**
 * Establishes the heap invariant (described above) in the entire tree,
 * assuming nothing about the order of the elements prior to the call.
 * This classic algorithm due to Floyd (1964) is known to be O(size).
 */
private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1;
    final Comparator<? super E> cmp;
    if ((cmp = comparator) == null)
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i], es, n);
    else
        for (; i >= 0; i--)
            siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}

The time complexity of $O(size)$ is also proven in Heap.

2 Other Methods

Apart from the core methods, this class also provides other useful methods. We will discuss some of them below.

2.1 bulkRemove()

This method takes an argument filter as input, removing all the elements filtered by this argument. Note that this is a private method. The exposed interface is removeIf(), removeAll() and retainAll().

/** Implementation of bulk remove methods. */
private boolean bulkRemove(Predicate<? super E> filter) {
    ...
}

/**
 * @throws NullPointerException {@inheritDoc}
 */
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    return bulkRemove(filter);
}

/**
 * @throws NullPointerException {@inheritDoc}
 */
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return bulkRemove(e -> c.contains(e));
}

/**
 * @throws NullPointerException {@inheritDoc}
 */
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return bulkRemove(e -> !c.contains(e));
}

The method first scans the whole array to check whether there is no matching element.

private boolean bulkRemove(Predicate<? super E> filter) {
    final int expectedModCount = ++modCount;
    final Object[] es = queue;
    final int end = size;
    int i;
    // Optimize for initial run of survivors
    for (i = 0; i < end && !filter.test((E) es[i]); i++)
        ;
    if (i >= end) {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        return false;
    }
    ...
}

modCount is a member used for concurrency scenarios. We will come to that later.

Then the indices of matching elements are stored in a bitmap.

    // Tolerate predicates that reentrantly access the collection for
    // read (but writers still get CME), so traverse once to find
    // elements to delete, a second pass to physically expunge.
    final int beg = i;
    final long[] deathRow = nBits(end - beg);
    deathRow[0] = 1L;   // set bit 0
    for (i = beg + 1; i < end; i++)
        if (filter.test((E) es[i]))
            setBit(deathRow, i - beg);
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

Fast and Slow Pointers is then used for removing: The fast pointer seeks for the unmatching elements after the first matching index beg, while the slow marks the matching elements. If there is no matching element, the slow pointer w will always equals the fast pointer i. When they reach a matching element, w pauses to mark its index and i continues. This mechanism allows the remaining unmatching elements will be moved to the “hollows” in the front and only takes one scan.

...
    int w = beg;
        for (i = beg; i < end; i++)
            if (isClear(deathRow, i - beg))
                es[w++] = es[i];
...

To this point, the fast pointer i has reached the end of the array, and w is pointing to the next index of newSize-1. So the elements after w are then purged and the size member is reset.

...
for (i = size = w; i < end; i++)
    es[i] = null;
...

At last, heapify() is called to ensure the rest of the collection makes a heap. Here’s the code of the whole method:

/** Implementation of bulk remove methods. */
private boolean bulkRemove(Predicate<? super E> filter) {
    final int expectedModCount = ++modCount;
    final Object[] es = queue;
    final int end = size;
    int i;
    // Optimize for initial run of survivors
    for (i = 0; i < end && !filter.test((E) es[i]); i++)
        ;
    if (i >= end) {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        return false;
    }
    // Tolerate predicates that reentrantly access the collection for
    // read (but writers still get CME), so traverse once to find
    // elements to delete, a second pass to physically expunge.
    final int beg = i;
    final long[] deathRow = nBits(end - beg);
    deathRow[0] = 1L;   // set bit 0
    for (i = beg + 1; i < end; i++)
        if (filter.test((E) es[i]))
            setBit(deathRow, i - beg);
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    int w = beg;
    for (i = beg; i < end; i++)
        if (isClear(deathRow, i - beg))
            es[w++] = es[i];
    for (i = size = w; i < end; i++)
        es[i] = null;
    heapify();
    return true;
}

2.2 contains()

/**
     * Returns {@code true} if this queue contains the specified element.
     * More formally, returns {@code true} if and only if this queue contains
     * at least one element {@code e} such that {@code o.equals(e)}.
     *
     * @param o object to be checked for containment in this queue
     * @return {@code true} if this queue contains the specified element
     */
    public boolean contains(Object o) {
        ...
    }

This method checks whether the heap contains an element. The method runs at $O(n)$ because there is no index used in this class. This also shows that it is not advised to search for an item in a Priority Queue. Other data structures like BinarySearchTree or HashMap should be used for these requirements.

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

private int indexOf(Object o) {
    if (o != null) {
        final Object[] es = queue;
        for (int i = 0, n = size; i < n; i++)
            if (o.equals(es[i]))
                return i;
    }
    return -1;
}

3 Designs

3.1 Concurrency-safe

This class uses a member modCount to ensure thread safety:

/**
     * The number of times this priority queue has been
     * <i>structurally modified</i>.  See AbstractList for gory details.
     */
    transient int modCount;     // non-private to simplify nested class access

Every time the element in the array changes, including adding element and removing element, the modCount will be added for version check. So methods involving reading or writing will first mark the right version of modCount. If the expected version doesn’t match the current modCount, it means the array is modified during the read/write process and thus throws an ConcurrentModificationException.
Example method forEach :

/**
 * @throws NullPointerException {@inheritDoc}
 */
public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    final Object[] es = queue;
    for (int i = 0, n = size; i < n; i++)
        action.accept((E) es[i]);
    if (expectedModCount != modCount)
        throw new ConcurrentModificationException();
}

3.2 Object Oriented

Java being an Object Oriented language, class PriorityQueue reflects many of its features, such as template class, inheritance and implementation.

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

3.2.1 Serializable

Classes implementing this interface can be serialized by JDK for IO transmission. This means this class is verified by Java to be safe to be transformed into/from byte array. The class declares its serialVersion to serialize/deserialize the correct version of objects:

...
@java.io.Serial
private static final long serialVersionUID = -7720805057305804111L;
...

3.2.2 AbstractQueue

PriorityQueue has a hierarchy of inheritance: Inheritance Hieraychy of PriorityQueue

• Iterable is an interface of which the implementation class can be the target of the enhanced for statement. Example:

        Iterable<Object> t = new ArrayList<>();
        for(Object o:t){
            action.accept(o);
        }
  

• Collection represents a group of objects. This interface is used for maximum generality to move specific implementations around, such as List, Set, etc.
• AbstractCollection provides a skeletal implementation of Collection interface by implementing its non-modifying methods like isEmpty(), contains() and toArray().
• Queue typically order elements in a FIFO(first-in-first-out) way but not always. PriorityQueue is an exception. Queue provides basic interfaces add(),offer(),poll(),remove(), element() and peek(). The pairs of similar methods differ only in return values - add(), remove() and element() will throw an exception if operation fails, while their pair method returns null or false.
• AbstractQueue provides skeletal implementations of Queue