Explication détaillée de la façon dont la file d'attente prioritaire est implémentée dans le JDK

Cet article présente principalement en détail la PriorityQueue du code source du JDK, qui a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Application de la file d'attente prioritaire

.

Les files d'attente prioritaires sont courantes dans le développement de programmes. Par exemple, lorsque le système d'exploitation planifie des processus, un algorithme réalisable consiste à utiliser des files d'attente prioritaires. Lorsqu'un nouveau processus est fork(), il est d'abord mis dans la file d'attente. le planificateur à l'intérieur du système d'exploitation est chargé de retirer en permanence les processus de priorité plus élevée de cette file d'attente prioritaire pour l'exécution ; le système d'exploration doit souvent également retirer les processus de haute priorité d'une file d'attente prioritaire boucle pendant l'exécution. Tâches de niveau et capture. Il est concevable que si de telles tâches ne sont pas divisées par priorité, le système échouera inévitablement. Par exemple, les processus peu prioritaires du système d'exploitation continuent d'occuper des ressources tandis que les processus hautement prioritaires attendent toujours dans la file d'attente. De plus, les files d’attente prioritaires ont également certaines applications dans les algorithmes gloutons.

2. Principe de mise en œuvre de la file d'attente prioritaire

La mise en œuvre de la file d'attente prioritaire consiste à utiliser la structure de tas binaire, qui doit satisfaire les deux propriétés suivantes (propriété Heap) , ici Prenez le petit tas supérieur comme exemple pour expliquer :

1. La valeur de tout nœud est inférieure ou égale à la valeur de son nœud enfant.
2. Tous les nœuds sont remplis de haut en bas et de gauche à droite, ce qui constitue un arbre binaire complet.

Sur la base de ces deux règles, le tas binaire utilise souvent un tableau dans l'implémentation. Étudions l'implémentation du tas binaire (file d'attente prioritaire) dans le JDK.

3. Comment la file d'attente prioritaire est implémentée dans le JDK

La meilleure façon d'étudier le code source est de déboguer et de voir les modifications des variables à chaque étape. Nous pouvons simplement écrire une démo et déboguer dans le code source pour le savoir :

Ici, nous créons simplement une file d'attente prioritaire et y ajoutons trois éléments. peut Créer un point d'arrêt par ligne. Si vous utilisez l'éditeur Eclipse , vous pouvez appuyer sur F5 pour saisir le code source :

Lorsque le code s'exécute ici, PriorityQueue appelle son propre constructeur

surchargé Le premier paramètre est la taille par défaut du tableau, et le second est le comparateur pour la comparaison des éléments. Notre démo ici est relativement simple. using Vous pouvez choisir d'implémenter votre propre comparateur lorsque vous utilisez des files d'attente prioritaires.

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

Ensuite, étudions le fonctionnement de l'offre lors de l'ajout d'éléments :

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

Expliquons-le ligne par ligne. Tout d'abord, la méthode d'offre détermine si le paramètre est vide. n'est pas vide, puis incrémentez la variable modCount. modCount enregistre le nombre de fois où la file d'attente a été modifiée. Ensuite, déterminez si le tableau franchira la limite. Si c'est le cas, développez-le via la croissance. L'élément est 0, placez l'élément directement dans le tableau. La première position, sinon effectuez une opération siftUp.

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

Le code ci-dessus étend la file d'attente. Le commentaire

dans le code source est également très clair. Tout d'abord, déterminez si la taille actuelle du tableau est suffisamment petite (<64). S'il est suffisamment petit, modifiez la taille Agrandissez à 2 fois, sinon ajoutez 50 % à la taille d'origine. Il convient de noter qu'à la fin, un jugement est porté sur la question de savoir si la taille dépasse.

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

Si la taille qui doit être étendue est déjà <0, elle a évidemment débordé et une exception OutOfMemory est levée ici.

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

Afin de garantir la propriété de file d'attente prioritaire 1, lors de l'insertion de chaque élément, il doit être comparé au parent du nœud pour trouver sa position correcte. Dans certains livres de structure de données, cette opération est effectuée. appelé filtrage vers le haut (percoler vers le haut).

L'opération de mise en file d'attente est terminée. Vient ensuite l'opération de retrait de la file d'attente, c'est-à-dire l'opération poll() :

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

Cette méthode prend d'abord le premier élément du tableau comme résultat. , (car s'il s'agit d'un petit tas supérieur, le haut du tas est toujours le plus petit élément), et place le dernier élément de la file d'attente en première position. Enfin, utilisez siftDown pour effectuer quelques ajustements afin de garantir les propriétés de. la file d'attente. Cette opération est appelée percoler vers le bas.

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

Comme le montre la figure ci-dessus, k est constamment comparé à ses fils pendant le processus de filtrage vers le bas. Si l'ordre de la file d'attente prioritaire est satisfait, la boucle est rompue.

[Recommandations associées]

1.

Tutoriels vidéo gratuits Java

2.

Analyse complète des annotations Java.

3.

Manuel du didacticiel FastJson

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!