Structures de données : Pyramide (Binary Heap) en Java

Salut Salut ! Personne ne niera que les algorithmes et les structures de données constituent le fondement indéniable de la programmation. Oui, vous pouvez travailler comme programmeur à leur insu, mais hélas, vous n’irez pas loin. Par conséquent, pour renforcer votre base de connaissances dans ce domaine, je voudrais parler d'une structure de données telle qu'une pyramide (également connue sous le nom de tas et tas binaire). En règle générale, de telles structures de données sont utilisées dans divers planificateurs et autres structures dans lesquelles il est nécessaire d'indiquer la priorité de diverses tâches. Alors... Une pyramide est un type d'arbre qui permet une insertion/suppression en un temps O(logN) et possède les propriétés suivantes :

• Complétude. Tous les niveaux de l'arbre contiennent tous les nœuds possibles sauf le dernier, qui ne peut être rempli que partiellement et qui est rempli de gauche à droite ;
• Une pyramide est généralement implémentée sur la base d'un tableau ;
• Pour chaque nœud de la pyramide, il existe une condition fondamentale selon laquelle la valeur de chaque nœud est supérieure (ou égale) aux valeurs de ses descendants. En conséquence, le maximum sera stocké dans l'élément supérieur.

Une pyramide constituée de sommets qui stockent des valeurs ne dépassant pas 10 : je voudrais noter que par rapport à un arbre de recherche binaire, une pyramide est faiblement ordonnée , puisque dans un arbre de recherche binaire la clé de l'enfant de gauche est inférieure à la clé du bon enfant, et dans une pyramide, une telle condition n’existe pas.

Supprimer un élément par index

Tout d'abord, regardons la séquence d'actions lors de la suppression d'un nœud sélectionné :

1. Supprimez le nœud sélectionné.
2. Déplacez le dernier nœud de la dernière ligne à la place de celui supprimé.
3. Déplacez-le vers le bas jusqu'à ce qu'il soit en dessous du nœud le plus grand et au-dessus du nœud le plus petit.

Lors de l'utilisation d'une pyramide, il est généralement nécessaire de pouvoir supprimer le sommet (l'élément zéro du tableau interne) ou le dernier (les opérations de déplacement peuvent alors être omises, ne laissant que la suppression de l'élément). À titre d'exemple de suppression d'un élément par index dans la pyramide que nous examinons ci-dessus, nous supprimerons le nœud de valeur 7 :

1. Nous supprimons le nœud sélectionné et plaçons à sa place le dernier, qui a une valeur de 4 :

   Mais dans cette position, ce nœud ne remplit pas la condition selon laquelle chaque nœud descendant ne doit pas être plus grand que celui en question, non ?

   C'est pourquoi:

2. On l'échange avec le plus grand des enfants, qui vaut 6 :

   Ensuite, nous regardons s'il existe des descendants avec une valeur supérieure à celle de notre élément déplacé, et nous voyons qu'il n'y en a pas, ce qui signifie que l'élément a pris sa place.

Insérer un nouvel élément

Quelles sont les actions lors de l'insertion d'un nouvel élément :

1. Le nœud inséré est placé au bout de la pyramide.

   Mais nous avons une condition selon laquelle un élément enfant ne peut pas avoir une valeur supérieure à celle de son parent, n'est-ce pas ?

   C'est pourquoi:

2. Comparez le nouvel élément avec l'élément parent. Si le nouvel élément est plus petit, alors l'opération est terminée ; sinon, il échange sa place avec l'élément parent. Après cela, il commence à être comparé au nouvel élément parent, et ainsi de suite... Jusqu'à ce que l'élément parent soit plus grand que le nouveau.

Par exemple, à la pyramide obtenue en supprimant un élément, nous souhaitons ajouter un élément de valeur 8 :

1. Placez un nouveau nœud au bout de la pyramide :

2. Comparez le nouvel élément avec l'élément parent, qui a une valeur de 4.

   Puisque le nouvel élément est plus grand que le parent, nous les échangeons :

3. Nous comparons le nouvel élément avec son nouveau parent et voyons que notre élément est plus grand que son (8>7), nous les échangeons donc également :

   Encore une fois, nous comparons l'élément avec l'élément parent et constatons que cette fois l'élément parent est plus grand, ce qui signifie que notre nouvel élément s'est mis en place.

Remplacer un élément

Lors du remplacement d'un élément, vous devez d'abord remplacer l'élément par l'index donné. Logique, non ? Quoi ensuite? Après tout, la nouvelle valeur de l'élément est déjà différente, et ce n'est pas un fait qu'elle correspond aux conditions de la pyramide. Autrement dit, ce n'est pas un fait que tous les éléments enfants sont plus petits que l'élément inséré. Ce n'est pas non plus un fait que les éléments parents sont plus grands que les nouveaux. Par conséquent, vous devez d'abord comparer avec l'ancienne valeur de l'élément :

• si le nouvel élément est plus grand que lui, alors nous devons le comparer avec les éléments parents et, si nécessaire, les échanger ;
• si le nouvel élément est plus petit, il doit alors être comparé au plus grand des éléments enfants et échangé si l'élément enfant est plus grand (jusqu'à ce que le nouvel élément soit à un emplacement valide).

Regardons cela en utilisant notre exemple. Nous voulons maintenant insérer un élément de valeur 1 au lieu d'un élément de valeur 9 :

1. Insérez l'élément à la place du précédent :
2. Nous comparons l'élément précédent 9 et le nouveau 1 et voyons qu'il est plus petit, ce qui signifie que nous allons essayer de le décaler vers le bas.
3. Nous le comparons avec le plus grand élément des enfants, c'est-à-dire avec celui qui a une valeur de 5, et nous voyons que le nouveau est plus petit. Par conséquent, nous échangeons les éléments comparés :
4. Puisqu'il n'y a plus de nouvel élément en dessous de notre nouveau, nous pouvons dire que l'élément s'est mis en place.

Implémentation d'une pyramide en Java

Après avoir compris le fonctionnement de cette structure, il est temps de s'intéresser à l'implémentation d'une pyramide en Java : Une classe représentant un sommet et la valeur qu'il contient :

public class Node {
  private int value;

  public Node(int value) {
     this.value = value;
  }

  public int getValue() {
     return this.value;
  }

  public void setValue(int value) {
     this.value = value;
  }
}

La classe représentant la pyramide elle-même :

public class Heap {
  private Node[] heapArray; // массив со всеми вершинами
  private int maxSize; // размер массива
  private int currentSize; // количество узлов массиве

  public Heap(int maxSize) { // создание пустой пирамиды
     this.maxSize = maxSize;
     this.currentSize = 0;
     heapArray = new Node[maxSize];
  }

  public void printHeap() { // отображение перамиды в консоль
     System.out.println("Массив значений: ");

     for (int n = 0; n < currentSize; n++) {
        if (heapArray[n] != null) {
           System.out.println(heapArray[n].getValue() + " ");
        }
        else {
           System.out.println("-");
        }
     }
     System.out.println();

     int countOfGaps = 32;
     int itemsPerRow = 1;
     int columnNumber = 0; // номер element в данной строке
     String lines = "___________________________________________________________________";
     System.out.println(lines);
     for (int i = 0; i < currentSize; i++) {
        if (columnNumber == 0) {  // проверяем первый элемент ли в текущей строке
           for (int k = 0; k < countOfGaps; k++) { // добавляем предшествующие пробелы
              System.out.print(' ');
           }
        }
        System.out.print(heapArray[i].getValue());// выводим в консоль meaning вершины

        if (++columnNumber == itemsPerRow) { // проверяем последний ли элемент в строке
           countOfGaps /= 2; // уменьшаем количество оступов применяемое для следующей строки
           itemsPerRow *= 2; // указываем, что элементов может быть вдвое больше
           columnNumber = 0; // сбрасываем счётчик для текущего element строки
           System.out.println(); // переходим на нову строку
        }
        else { //переход к следующему элементу
           for (int k = 0; k < countOfGaps * 2 - 2; k++) {
              System.out.print(' '); // добавляем оступы
           }
        }
     }
     System.out.println("\n" + lines); // нижний пункир
  }

  public boolean insertNode(int value) { // вставка нового значения
     if (currentSize == maxSize) { // проверяем не выходим ли мы за рамки массива
        return false;
     }
     Node newNode = new Node(value);// создание вершины с данным meaningм
     heapArray[currentSize] = newNode;// вершину задём в самый низ дерева
     displaceUp(currentSize++);// пытаемся поднять вершину, если meaning вершины позволяет
     return true;
  }

  public Node removeNode(int index) { // удалить элемент по индексу массива
     if(index > 0 && currentSize > index) {
        Node root = heapArray[index];
        heapArray[index] = heapArray[--currentSize]; // задаём элементу с переданным индексом, meaning последнего element
        heapArray[currentSize] = null;// последний элемент удаляем
        displaceDown(index);// проталкиваем вниз новый элемент, чтобы он должное ему место
        return root;
     }
     return null;
  }

  public boolean changeNode(int index, int newValue) {
     if (index < 0 || currentSize<=index) {
        return false;
     }
     int oldValue = heapArray[index].getValue(); // сохраняем старое meaning
     heapArray[index].setValue(newValue); // присваиваем новое

     if (oldValue < newValue) {// если узел повышается
        displaceUp(index);     // выполняется смещение вверх
     }
     else {                  // если понижается
        displaceDown(index);   // смещение вниз
     }
     return true;
  }

  private void displaceUp(int index) { //смещение вверх
     int parentIndex = (index - 1) / 2; // узнаем индекс родителя
     Node bottom = heapArray[index]; // берем элемент
     while (index > 0 && heapArray[parentIndex].getValue() < bottom.getValue()) {// если родительский элемент меньше
        heapArray[index] = heapArray[parentIndex];// то меняем его местами с рассматриваемым
        index = parentIndex;
        parentIndex = (parentIndex - 1) / 2;// берем новый родительский индекс и повторяем сравнение элементов
     }
     heapArray[index] = bottom;// соохраняем результат
  }

  private void displaceDown(int index) {// смещение вниз
     int largerChild;
     Node top = heapArray[index]; // сохранение корня, пока у узла есть хотя бы один потомок
     while (index < currentSize / 2) {// если данное condition не выполняется то элемент уже в самом низу пирамиды
        int leftChild = 2 * index + 1; // вычисляем индексы в массиве для левого узла ребенка
        int rightChild = leftChild + 1;// и правого

        if (rightChild < currentSize && heapArray[leftChild].getValue() < heapArray[rightChild].getValue()) {
           largerChild = rightChild;
        }// вычисляем ребенка вершину с наибольшим числовым meaningм
        else {
           largerChild = leftChild;
        }

        if (top.getValue() >= heapArray[largerChild].getValue()) {// если meaning вершины больше or равно
           //значени его наибольшего ребенка
           break;// то выходим из метода
        }

        heapArray[index] = heapArray[largerChild];// заменяем вершину, большей дочерней вершиной
        index = largerChild; // текущий индекс переходит вниз
     }
     heapArray[index] = top; // задаем конечное местоположение для element
  }
}

Enfin, regardons notre pyramide en action :

public class Solution {

  public static void main(String[] args) {
     // задаем начальные данные:
     Heap heap = new Heap(31);
     heap.insertNode(120);
     heap.insertNode(40);
     heap.insertNode(50);
     heap.insertNode(80);
     heap.insertNode(20);
     heap.insertNode(100);
     heap.insertNode(150);
     heap.insertNode(30);
     heap.insertNode(210);
     heap.insertNode(180);
     heap.insertNode(10);
     heap.insertNode(90);
      // выводим начальную пирамиду в консоль
     heap.printHeap();

Sortie de la console :

// изменяем элемент под индексом 0 с 210 на 15, и выводим в консоль измененную пирамиду
     heap.changeNode(0,15);
     heap.printHeap();

Sortie de la console :

// удаляем элемент под индексом 3, который имеет meaning 80 и смотрим на изменившуюся пирамиду
     heap.removeNode(3);
     heap.printHeap();
  }
}

Sortie de la console : Eh bien, c'est tout. Merci à tous pour votre attention !