Estructuras de datos: pirámide (montón binario) en Java

Hola hola! Nadie negará que los algoritmos y las estructuras de datos son la base innegable de la programación. Sí, puedes trabajar como programador sin su conocimiento, pero, lamentablemente, no llegarás muy lejos. Por lo tanto, para fortalecer su base de conocimientos en esta área, me gustaría hablar sobre una estructura de datos como una pirámide (también conocida como montón y montón binario). Como regla general, estas estructuras de datos se utilizan en varios programadores y otras estructuras en las que es necesario indicar la prioridad de varias tareas. Entonces... Una pirámide es un tipo de árbol que proporciona inserción/eliminación en tiempo O(logN) y tiene las siguientes propiedades:

• Lo completo. Todos los niveles del árbol contienen todos los nodos posibles excepto el último, que sólo se puede llenar parcialmente y que se llena de izquierda a derecha;
• Una pirámide generalmente se implementa en base a una matriz;
• Para cada nodo de la pirámide, existe una condición fundamental de que el valor de cada nodo sea mayor (o igual) que los valores de sus descendientes. En consecuencia, el máximo se almacenará en el elemento superior.

Una pirámide que consta de vértices que almacenan valores no superiores a 10: me gustaría señalar que, en comparación con un árbol de búsqueda binario, una pirámide está débilmente ordenada , ya que en un árbol de búsqueda binario la clave del hijo izquierdo es menor que la clave del hijo correcto, y en una pirámide no existe tal condición.

Eliminar un elemento por índice

Primero, veamos la secuencia de acciones al eliminar un nodo seleccionado:

1. Eliminar el nodo seleccionado.
2. Mueva el último nodo de la última fila al lugar del eliminado.
3. Muévalo hacia abajo hasta que esté debajo del nodo más grande y encima del más pequeño.

Cuando se utiliza una pirámide, generalmente es necesario poder eliminar la parte superior (el elemento cero de la matriz interna) o el último (entonces se pueden omitir las operaciones de movimiento, dejando solo la eliminación del elemento). Como ejemplo de eliminación de un elemento por índice en la pirámide que estamos viendo arriba, eliminaremos el nodo con valor 7:

1. Eliminamos el nodo seleccionado y colocamos en su lugar el último que tiene un valor de 4:

   Pero en esta posición, este nodo no cumple la condición de que cada nodo descendiente no debe ser mayor que el en cuestión, ¿verdad?

   Es por eso:

2. Lo intercambiamos con el mayor de los hijos, que tiene un valor de 6:

   A continuación miramos si hay algún descendiente con un valor mayor que el de nuestro elemento desplazado, y vemos que no hay ninguno, lo que significa que el elemento ha tomado su lugar.

Insertando un nuevo elemento

¿Cuáles son las acciones al insertar un nuevo elemento?

1. El nodo insertado se coloca al final de la pirámide.

   Pero tenemos la condición de que un elemento hijo no puede tener un valor mayor que su padre, ¿verdad?

   Es por eso:

2. Compare el nuevo elemento con el elemento padre. Si el nuevo elemento es más pequeño, entonces la operación se completa; si no, entonces intercambia lugares con el elemento padre. Después de eso, comienza a compararse con el nuevo elemento padre, y así sucesivamente... Hasta que el elemento padre sea mayor que el nuevo.

Por ejemplo, a la pirámide que se obtuvo quitando un elemento, queremos agregarle un elemento con el valor 8:

1. Coloque un nuevo nodo al final de la pirámide:

2. Compare el nuevo elemento con el elemento principal, que tiene un valor de 4.

   Como el nuevo elemento es más grande que el padre, los intercambiamos:

3. Comparamos el nuevo elemento con su nuevo padre y vemos que nuestro elemento es más grande que su (8>7), así que también los intercambiamos:

   Nuevamente comparamos el elemento con el elemento padre y vemos que esta vez el elemento padre es más grande, lo que significa que nuestro nuevo elemento ha encajado en su lugar.

Reemplazo de un elemento

Al reemplazar un elemento, primero debe reemplazar el elemento con el índice dado. Lógico, ¿verdad? Entonces, ¿qué sigue? Después de todo, el nuevo valor del elemento ya es diferente, y no es un hecho que corresponda a las condiciones de la pirámide. Es decir, no es un hecho que todos los elementos secundarios sean más pequeños que el elemento insertado. Tampoco es un hecho que los elementos principales sean más grandes que el nuevo. Por lo tanto, primero es necesario comparar con el valor anterior del elemento:

• si el nuevo elemento es más grande que él, entonces debemos compararlo con los elementos principales y, si es necesario, intercambiarlos;
• si el nuevo elemento es más pequeño, debe compararse con el mayor de los elementos secundarios e intercambiarse si el elemento secundario es más grande (hasta que el nuevo elemento esté en un lugar válido).

Veamos esto usando nuestro ejemplo. Ahora queremos insertar un elemento con valor 1 en lugar de un elemento con valor 9:

1. Inserta el elemento en lugar del anterior:
2. Comparamos el elemento anterior 9 y el nuevo 1 y vemos que es más pequeño, por lo que intentaremos desplazarlo hacia abajo.
3. Lo comparamos con el elemento más grande de los hijos, es decir, con el que tiene valor 5, y vemos que el nuevo es más pequeño. Por tanto, intercambiamos los elementos comparados:
4. Como ahora no hay elementos nuevos debajo del nuevo, podemos decir que el elemento ha encajado en su lugar.

Implementación de una pirámide en Java.

Después de entender cómo funciona esta estructura, es hora de ver la implementación de una pirámide en Java : una clase que representa un vértice y el valor que 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 clase que representa la pirámide misma:

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; // номер elemento в данной строке
     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());// выводим в консоль significado вершины

        if (++columnNumber == itemsPerRow) { // проверяем последний ли элемент в строке
           countOfGaps /= 2; // уменьшаем количество оступов применяемое для следующей строки
           itemsPerRow *= 2; // указываем, что элементов может быть вдвое больше
           columnNumber = 0; // сбрасываем счётчик для текущего elemento строки
           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);// создание вершины с данным significadoм
     heapArray[currentSize] = newNode;// вершину задём в самый низ дерева
     displaceUp(currentSize++);// пытаемся поднять вершину, если significado вершины позволяет
     return true;
  }

  public Node removeNode(int index) { // удалить элемент по индексу массива
     if(index > 0 && currentSize > index) {
        Node root = heapArray[index];
        heapArray[index] = heapArray[--currentSize]; // задаём элементу с переданным индексом, significado последнего elemento
        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(); // сохраняем старое significado
     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) {// если данное condición не выполняется то элемент уже в самом низу пирамиды
        int leftChild = 2 * index + 1; // вычисляем индексы в массиве для левого узла ребенка
        int rightChild = leftChild + 1;// и правого

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

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

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

Finalmente, veamos nuestra pirámide en acción:

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

Salida de consola:

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

Salida de consola:

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

Salida de la consola: Bueno, eso es todo. ¡Gracias a todos por su atención!