Strutture dati: piramide (heap binario) in Java

Ciao Ciao! Nessuno negherà che gli algoritmi e le strutture dati siano il fondamento innegabile della programmazione. Sì, puoi lavorare come programmatore senza conoscerli, ma ahimè, non andrai lontano. Pertanto, per rafforzare la tua conoscenza in questo ambito, vorrei parlarti di una struttura dati chiamata piramide (nota anche come heap e heap binario). Di norma, tali strutture dati vengono utilizzate in vari pianificatori e altre strutture in cui è necessario indicare la priorità di vari compiti. Quindi... Una piramide è un tipo di albero che prevede l'inserimento/cancellazione in tempo O(logN) e ha le seguenti proprietà:

• Completezza. Tutti i livelli dell'albero contengono tutti i nodi possibili tranne l'ultimo, che può essere riempito solo parzialmente e che si riempie da sinistra a destra;
• Una piramide viene solitamente implementata in base a un array;
• Per ogni nodo della piramide esiste la condizione fondamentale che il valore di ciascun nodo sia maggiore (o uguale) ai valori dei suoi discendenti. Di conseguenza, il massimo verrà memorizzato nell'elemento superiore.

Una piramide composta da vertici che memorizzano valori non superiori a 10: vorrei notare che rispetto ad un albero binario di ricerca, una piramide è debolmente ordinata , poiché in un albero binario di ricerca la chiave del figlio di sinistra è minore della chiave del bambino giusto, e in una piramide non esiste tale condizione.

Rimozione di un elemento tramite indice

Innanzitutto, diamo un'occhiata alla sequenza di azioni durante l'eliminazione di un nodo selezionato:

1. Elimina il nodo selezionato.
2. Sposta l'ultimo nodo dell'ultima riga nella posizione di quello eliminato.
3. Spostalo verso il basso finché non si trova sotto il nodo più grande e sopra quello più piccolo.

Quando si utilizza una piramide, solitamente è necessario poter rimuovere il vertice (l'elemento zero dell'array interno) o l'ultimo (quindi le operazioni di spostamento possono essere omesse, lasciando solo la rimozione dell'elemento). Come esempio di eliminazione di un elemento per indice nella piramide che stiamo guardando sopra, elimineremo il nodo con valore 7:

1. Eliminiamo il nodo selezionato e posizioniamo al suo posto l'ultimo, che ha valore 4:

   Ma in questa posizione, questo nodo non soddisfa la condizione che ciascun nodo discendente non debba essere più grande di quello in questione, giusto?

   Ecco perché:

2. Lo scambiamo con il più grande dei figli, che ha valore 6:

   Successivamente, vediamo se ci sono discendenti con un valore maggiore di quello del nostro elemento spostato e vediamo che non ce ne sono, il che significa che l'elemento ha preso il suo posto.

Inserimento di un nuovo elemento

Quali sono le azioni quando si inserisce un nuovo elemento:

1. Il nodo inserito è posto all'estremità della piramide.

   Ma abbiamo la condizione che un elemento figlio non possa avere un valore maggiore del suo genitore, giusto?

   Ecco perché:

2. Confronta il nuovo elemento con l'elemento genitore. Se il nuovo elemento è più piccolo l'operazione è completata; altrimenti si scambia di posto con l'elemento genitore. Successivamente, inizia a essere confrontato con il nuovo elemento genitore e così via... finché l'elemento genitore non diventa maggiore di quello nuovo.

Ad esempio, alla piramide ottenuta eliminando un elemento, vogliamo aggiungere un elemento con il valore 8:

1. Posiziona un nuovo nodo all'estremità della piramide:

2. Confronta il nuovo elemento con l'elemento genitore, che ha un valore pari a 4.

   Poiché il nuovo elemento è più grande del genitore, li scambiamo:

3. Confrontiamo il nuovo elemento con il suo nuovo genitore e vediamo che il nostro elemento è più grande del suo (8>7), quindi scambiamo anche loro:

   Ancora una volta confrontiamo l'elemento con l'elemento genitore e vediamo che questa volta l'elemento genitore è più grande, il che significa che il nostro nuovo elemento è andato a posto.

Sostituzione di un elemento

Quando si sostituisce un elemento, è necessario prima sostituire l'elemento con l'indice specificato. Logico, vero? Quindi che succede adesso? Dopotutto, il nuovo valore dell'elemento è già diverso e non è un dato di fatto che corrisponda alle condizioni della piramide. Cioè, non è un dato di fatto che tutti gli elementi figlio siano più piccoli dell'elemento inserito. Inoltre, non è un dato di fatto che gli elementi principali siano più grandi di quello nuovo. Pertanto, devi prima confrontare con il vecchio valore dell'elemento:

• se il nuovo elemento è più grande di esso, allora dobbiamo confrontarlo con gli elementi genitori e, se necessario, scambiarli;
• se il nuovo elemento è più piccolo, allora deve essere confrontato con il più grande degli elementi figli e scambiato se l'elemento figlio è più grande (finché il nuovo elemento non si trova in una posizione valida).

Diamo un'occhiata a questo usando il nostro esempio. Ora vogliamo inserire un elemento con valore 1 invece di un elemento con valore 9:

1. Inserisci l'elemento al posto del precedente:
2. Confrontiamo l'elemento precedente 9 e quello nuovo 1 e vediamo che è più piccolo, il che significa che proveremo a spostarlo verso il basso.
3. Lo confrontiamo con l'elemento più grande dei figli, cioè con quello che ha valore 5, e vediamo che quello nuovo è più piccolo. Pertanto, scambiamo gli elementi confrontati:
4. Dato che ora non ci sono nuovi elementi sotto il nostro nuovo, possiamo dire che l'elemento è andato a posto.

Implementazione di una piramide in Java

Dopo aver compreso come funziona questa struttura, è tempo di esaminare l'implementazione di una piramide in Java : una classe che rappresenta un vertice e il valore che contiene:

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 che rappresenta la piramide stessa:

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

Infine, diamo un'occhiata alla nostra piramide in azione:

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

Uscita console:

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

Uscita console:

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

Output della console: Bene, questo è tutto. Grazie a tutti per l'attenzione!