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 :

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

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

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

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

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

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

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

Tutoriels vidéo gratuits Java

Analyse complète des annotations Java.

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!