Detaillierte Erläuterung, wie die Prioritätswarteschlange im JDK implementiert wird

In diesem Artikel wird hauptsächlich die PriorityQueue des JDK-Quellcodes vorgestellt, die einen bestimmten Referenzwert hat

1. Anwendung der Prioritätswarteschlange Prioritätswarteschlangen sind in der Programmentwicklung üblich. Wenn das Betriebssystem beispielsweise Prozesse plant, wird ein neuer Prozess zuerst in die Warteschlange gestellt. Der Scheduler im Betriebssystem ist dafür verantwortlich, kontinuierlich Prozesse mit höherer Priorität aus dieser Prioritätswarteschlange zur Ausführung zu entfernen. Das Crawler-System muss während der Ausführung häufig auch Prozesse mit hoher Priorität aus einer Prioritätswarteschlange

Schleife

entfernen. Aufgaben nivellieren und erfassen. Es ist denkbar, dass das System unweigerlich ausfällt, wenn Aufgaben wie diese nicht nach Priorität aufgeteilt werden. Beispielsweise belegen Prozesse mit niedriger Priorität im Betriebssystem weiterhin Ressourcen, während Prozesse mit hoher Priorität immer in der Warteschlange warten. Darüber hinaus gibt es auch einige Anwendungen für Prioritätswarteschlangen in gierigen Algorithmen.

2. Implementierungsprinzip der Prioritätswarteschlange

Die Implementierung der Prioritätswarteschlange besteht darin, die binäre Heap-Struktur zu verwenden, die die folgenden zwei Eigenschaften (Heap-Eigenschaft) erfüllen muss. , hier Nehmen Sie zur Erläuterung den kleinen oberen Heap als Beispiel:

1. Der Wert eines beliebigen Knotens ist kleiner oder gleich dem Wert seines untergeordneten Knotens.

2. Alle Knoten werden von oben nach unten und von links nach rechts ausgefüllt, was einen vollständigen Binärbaum darstellt.
Basierend auf diesen beiden Regeln verwendet der Binärheap häufig ein

Array

in der Implementierung. Schauen wir uns die Implementierung des Binärheaps (Prioritätswarteschlange) im JDK an.

3. Wie die Prioritätswarteschlange im JDK implementiert wird

Der beste Weg, den Quellcode zu studieren, ist das Debuggen und Sehen der Änderungen von

Variablen

Bei jedem Schritt können wir einfach eine Demo schreiben und in den Quellcode debuggen, um Folgendes herauszufinden:

Hier erstellen wir einfach eine Prioritätswarteschlange und fügen ihr drei Elemente hinzu Wenn Sie den

Eclipse

Editor verwenden, können Sie F5 drücken, um den Quellcode einzugeben:

Wenn der Code hier ausgeführt wird, ruft PriorityQueue seinen eigenen

überladenen

-Konstruktor auf, und der zweite ist der Komparator für den Elementvergleich using Sie können Ihren eigenen Komparator implementieren, wenn Sie Prioritätswarteschlangen verwenden.

Als nächstes untersuchen wir die Angebotsoperation beim Hinzufügen von Elementen:

 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;
  }

Erklären wir es zunächst Zeile für Zeile. Die Angebotsmethode bestimmt, ob der Parameter leer ist ist nicht leer, dann wird die Variable modCount erhöht. Als nächstes wird ermittelt, ob das Array die Grenze überschreitet. Wenn dies der Fall ist, fügen Sie Elemente hinzu Element ist 0, platzieren Sie das Element direkt an der ersten Position, andernfalls führen Sie eine SiftUp-Operation aus.

 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;
  }

Der obige Code erweitert die Warteschlange. Der

 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);

Kommentar

im Quellcode ist ebenfalls sehr klar. Stellen Sie zunächst fest, ob die aktuelle Array-Größe klein genug ist (<64). Wenn es klein genug ist, ändern Sie die Größe Erweitern auf das Zweifache, andernfalls addieren Sie 50 % zur Originalgröße. Es ist zu beachten, dass hier am Ende beurteilt wird, ob die Größe überläuft.

Wenn die Größe, die erweitert werden muss, bereits <0 ist, ist offensichtlich ein Überlauf aufgetreten und hier wird eine OutOfMemory-Ausnahme ausgelöst.

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

Um die Prioritätswarteschlangeneigenschaft 1 sicherzustellen, muss beim Einfügen jedes Elements es mit dem übergeordneten Knoten verglichen werden, um seine korrekte Position zu finden. In einigen Datenstrukturbüchern ist dieser Vorgang erforderlich sogenannte Aufwärtsfilterung (nach oben versickern).

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;
  }

Der Enqueue-Vorgang ist abgeschlossen. Als nächstes folgt der Dequeue-Vorgang, also der poll()-Vorgang:

Diese Methode verwendet zunächst das erste Element des Arrays als Ergebnis , (denn wenn es sich um einen kleinen oberen Heap handelt, ist der obere Teil des Heaps immer das kleinste Element) und setzt das letzte Element der Warteschlange an die erste Position. Nehmen Sie abschließend mit siftDown einige Anpassungen vor, um die Eigenschaften sicherzustellen Die Warteschlange wird als „Percolate Down“ bezeichnet.

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;
  }

Wie in der Abbildung oben gezeigt, wird k während des Abwärtsfilterungsprozesses ständig mit seinem Sohn verglichen. Wenn die Reihenfolge der Prioritätswarteschlange erfüllt ist, wird die Schleife unterbrochen.

 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;
  }

[Verwandte Empfehlungen]

1.

Kostenlose Java-Video-Tutorials

2. Umfassende Analyse von Java-Annotationen

3. FastJson Tutorial-Handbuch

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung, wie die Prioritätswarteschlange im JDK implementiert wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!