Detailed explanation of how priority queue is implemented in JDK

This article mainly introduces the PriorityQueue of the JDK source code in detail, which has certain reference value. Interested friends can refer to it

1. Application of priority queue

Priority queues are common in program development. For example, when the operating system schedules processes, a feasible algorithm is to use priority queues. When a new process is fork()ed, it is first put into the queue. Finally, the Scheduler inside the operating system is responsible for continuously taking out higher-priority processes from this priority queue for execution; the crawler system often also needs to take out high-priority processes from a priority queue when executing.Loop Level tasks and capture. It is conceivable that if tasks like this are not divided by priority, the system will inevitably fail. For example, low-priority processes in the operating system continue to occupy resources while high-priority processes are always waiting in the queue. In addition, priority queues also have some applications in greedy algorithms.

2. Implementation principle of priority queue

The implementation of priority queue is to use the structure of binary heap, which needs to meet the following two properties (Heap property), here Take the small top heap as an example to explain:

1. The value of any node is less than or equal to the value of its child node.
　2. All nodes are filled in from top to bottom and from left to right, which is a complete binary tree.

Based on these two rules, binary heap often uses an array in its implementation. Let's study the implementation of binary heap (priority queue) in JDK.

3. How priority queue is implemented in JDK

The best way to study the source code is to debug and look at the changes in variables at each step. We can simply write a Demo and debug into the source code to find out:

Here we simply create a priority queue and add three elements to it. We can Make a breakpoint per line. If you use the Eclipse editor, you can then press F5 to enter the source code:

When the code runs here, PriorityQueue calls one of its own overloaded constructors. The first parameter is the default size of the array, and the second is the Comparator for element comparison. Our Demo here is relatively simple. You are using You can choose to implement your own Comparator when using priority queues.

 public PriorityQueue(int initialCapacity,
             Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
      throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
  }

Next, let’s study the offer operation when adding elements:

 public boolean offer(E e) {
    if (e == null)
      throw new NullPointerException();
    //记录了队列被修改的次数
    modCount++;
    int i = size;
    if (i >= queue.length)
      //扩容
      grow(i + 1);
    //增加元素个数
    size = i + 1;
    if (i == 0) 
      //第一次添加元素，直接放到第0个位置即可
      queue[0] = e;
    else
      //需要将元素放到最后，再做上滤操作
      siftUp(i, e);
    return true;
  }

Let’s explain it line by line. First, the offer method determines whether the parameter is empty. If it is not empty, it will automatically modify the variable modCount. Increase, modCount records the number of times the queue has been modified. Next, determine whether the array will go out of bounds. If it goes out of bounds, expand it through grow. Next, add elements. If the current element is 0, put the element directly into the first position of the array. , otherwise perform a siftUp operation.

 private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                     (oldCapacity + 2) :
                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
    //元素拷贝
    queue = Arrays.copyOf(queue, newCapacity);

The above code expands the queue. The comment in the source code is also very clear. First, determine whether the current array size is small enough (<64). If it is small enough, expand the size to 2 times, otherwise add 50% to the original size. It should be noted that a judgment is made at the end whether the size overflows.

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

If the size that needs to be expanded is already <0, it has obviously overflowed, and an OutOfMemory exception is thrown here.

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
      //计算父亲节点的下标
      int parent = (k - 1) >>> 1;
      Object e = queue[parent];
      //与父节点进行比较
      if (comparator.compare(x, (E) e) >= 0)
        break;
      queue[k] = e;
      k = parent;
    }
    queue[k] = x;
  }

In order to ensure the property of the priority queue 1, when inserting each element, it needs to be compared with the parent of the node to find its correct position. In some data structure books, this operation is called percolate up).

The enqueue operation has been finished, the next step is the dequeue operation, that is, the poll() operation:

public E poll() {
    if (size == 0)
      return null;
    int s = --size;
    //自增变量，代表队列修改次数
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
      siftDown(0, x);
    return result;
  }

This method first takes the first element of the array as the result, (because if it is a small If the top of the heap is always the smallest element), put the last element of the queue into the first position, and finally use siftDown to make some adjustments to ensure the properties of the queue. This operation is called percolate down.

 private void siftDownUsingComparator(int k, E x) {
 

    int half = size >>> 1;
    //这里k必须有孩子，故叶节点需要比较
    while (k < half) {
      //以下几行代码到较小的那个儿子,用变量c表示
      int child = (k << 1) + 1;
      //这里假设左儿子比较小
      Object c = queue[child];
      int right = child + 1;
      //左右儿子比较，如果右儿子小则将c赋值为右儿子
      if (right < size &&
        comparator.compare((E) c, (E) queue[right]) > 0)
        c = queue[child = right];
      //如果x比小儿子还小，说明k就是正确位置
      if (comparator.compare(x, (E) c) <= 0)
        break;
      queue[k] = c;
      k = child;
    }
    queue[k] = x;
  }

As shown in the figure above, k is constantly compared with its son during the downward filtering process. If the order of the priority queue is satisfied, the loop is broken.

【Related recommendations】

1. Free Java video tutorial

2. Comprehensive analysis of Java annotations

3. FastJson Tutorial Manual

The above is the detailed content of Detailed explanation of how priority queue is implemented in JDK. For more information, please follow other related articles on the PHP Chinese website!