Java set PriorityQueue source analysis

The problem

(1) What is a priority queue?

(2) How to implement a priority queue?

(3) Is PriorityQueue thread safe?

(4) Is PriorityQueue ordered?

Introduction to the

A priority queue is a collection of 0 or more elements. Each element in the collection has a weight value. Each queue will pop up the element with the highest or lowest priority.

In general, priority queues are implemented using a heap.

Remember what you know about stacks? Please, don’t ask me heap (sort) in the interview! .

So how does Java implement priority queues through the data structure “heap”?

Let’s study together.

Source code analysis

The main properties

// Default capacity
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// Where to store elements
transient Object[] queue; // non-private to simplify nested class access
// Number of elements
private int size = 0;
/ / the comparator
private final Comparator<? super E> comparator;
// Number of changes
transient int modCount = 0; // non-private to simplify nested class access

Copy the code

(1) The default capacity is 11;

(2) Queue, the elements are stored in arrays, which is the same as we said before.

(3) In the priority queue, there are also two ways to compare elements, one is the natural order of elements, the other is to compare through the comparator;

(4) modCount, number of changes, PriorityQueue is fast-fail;

For those of you who don’t know about fast-Fail, check out the Easter egg section of this article: Source code analysis of HashSet Java collections.

The team

There are two methods to join the team, add(E E) and offer(E E), which are identical, and add(E E) is also the offer(E E) called.

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    // Null elements are not supported
    if (e == null)
        throw new NullPointerException();
    modCount++;
    / / get the size
    int i = size;
    // The number of elements reaches the maximum
    if (i >= queue.length)
        grow(i + 1);
    // The number of elements increases by 1
    size = i + 1;
    // If there are no elements yet
    // Insert directly into the first position of the array
    // This is different from the heap we talked about before
    // Start with 0 in Java
    // We say that the heap starts at 1
    if (i == 0)
        queue[0] = e;
    else
        // Otherwise, insert the element to the size of the array, which is the next digit from the last element
        // Note that size is not the size of the array, but the number of elements
        // Then, do bottom-up heap
        siftUp(i, e);
    return true;
}

private void siftUp(int k, E x) {
    // Depending on whether there is a comparator, different methods are used
    if(comparator ! =null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        // Locate the parent node
        // Since the element starts at 0, subtract 1 and divide by 2
        int parent = (k - 1) > > >1;
        // The value of the parent
        Object e = queue[parent];
        // Compare the value of the inserted element with that of the parent node
        // If it is larger than the parent node, the loop is broken
        // Otherwise switch places
        if (key.compareTo((E) e) >= 0)
            break;
        // Switch places with the parent node
        queue[k] = e;
        // Now the inserted element is moved to the parent node
        // Continue the comparison with the parent node
        k = parent;
    }
    // Finally find the place to insert the element
    queue[k] = key;
}
Copy the code

(1) Null elements are not allowed to join the team;

(2) If the array is not enough, expand first;

(3) If there is no element already, insert the position with subscript 0;

(4) If there is an element, insert it one place after the last element.

(5) Heap from bottom to top and compare with the parent node;

(6) If it is smaller than the parent node, it will switch positions with the parent node until it is larger than the parent node;

(7) PriorityQueue is a small top heap.

capacity

private void grow(int minCapacity) {
    / / the old capacity
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    // When the old capacity is less than 64, the capacity is doubled
    If the old capacity is greater than or equal to 64, the capacity is increased by half
    int newCapacity = oldCapacity + ((oldCapacity < 64)? (oldCapacity +2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    // Check for overflow
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
        
    // Create a new array with a new size and copy the elements of the old array
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
Copy the code

(1) When the array is small (less than 64), the capacity is doubled each time;

(2) When the array is large, the capacity is increased by half each time;

Out of the team

There are two methods to exit the queue, remove() and poll(). Remove () is also a poll() call that throws an exception if there are no elements.

public E remove(a) {
    // call poll to pop up the header element
    E x = poll();
    if(x ! =null)
        // Return the popup element if there is one
        return x;
    else
        // Throw an exception without an element
        throw new NoSuchElementException();
}

@SuppressWarnings("unchecked")
public E poll(a) {
    // If size is 0, there are no elements
    if (size == 0)
        return null;
    // Pop up elements, the number of elements minus 1
    int s = --size;
    modCount++;
    // The first element of the queue
    E result = (E) queue[0];
    // The end of the queue
    E x = (E) queue[s];
    // Remove the last element of the queue
    queue[s] = null;
    // If there is an element after the popup element
    if(s ! =0)
        // Move the last element of the queue to the top of the queue
        // Do a top-down heap
        siftDown(0, x);
    // Returns the pop-up element
    return result;
}

private void siftDown(int k, E x) {
    // Select different methods depending on whether there is a comparator
    if(comparator ! =null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    // Only half of the elements need to be compared, since leaves make up half of the elements
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        // Find the location of the child node. Add 1 because the element starts at position 0
        int child = (k << 1) + 1; // assume left child is least
        // Value of the left child
        Object c = queue[child];
        // The position of the right child node
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            // Take the smaller of the left and right nodes
            c = queue[child = right];
        // If smaller than the child node, end
        if (key.compareTo((E) c) <= 0)
            break;
        // If larger than the smallest child node, swap places
        queue[k] = c;
        // The pointer moves to the smallest node and continues the comparison
        k = child;
    }
    // Find the right place to put the element
    queue[k] = key;
}
Copy the code

(1) Eject the first element of the queue;

(2) Move the end of the queue to the beginning of the queue;

(3) Heap from top to bottom and compare with the smallest child node all the way down;

(4) If it is larger than the smallest child node, it will switch positions and continue to compare with the smallest child node;

(5) If it is smaller than the smallest child node, there is no need to swap positions, and the heap is finished;

(6) This is the deletion of the heaptop element in the heap;

Take the team leader element

There are two methods for fetching the top element, Element () and peek(). Element () also calls peek(), except that it throws an exception if no element is fetched.

public E element(a) {
    E x = peek();
    if(x ! =null)
        return x;
    else
        throw new NoSuchElementException();
}
public E peek(a) {
    return (size == 0)?null : (E) queue[0];
}
Copy the code

(1) If there are elements, take the element with subscript 0;

(3) Return null if there are no elements, element() throws an exception;

conclusion

(1) PriorityQueue is a small top heap;

(2) PriorityQueue is not thread-safe;

(3) PriorityQueue is not ordered, only the top of the heap stores the smallest elements;

(4) Queuing is the implementation of the insert element of the heap;

(5) Queue out is the realization of the deleted elements of the heap;

(6) Still don’t understand heap? Take a look at this article [Please, stop asking me about stacks in interviews!] .

eggs

(1) Which methods in Queue?

Queue is the top-level interface to all queues, and it defines a bunch of methods. What’s the difference between them?

operation	An exception is thrown	Return a specific value
The team	add(e)	Offer (e) – false
Out of the team	remove()	Poll (), null
check	element()	Peek (), null

(2) Why is the add(e) method in PriorityQueue not checked for exceptions?

Because PriorityQueue is a queue that grows indefinitely and expands when it runs out of elements, adding elements doesn’t fail.

---

Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.