Estruturas de dados: pirâmide (pilha binária) em Java

Olá, olá! Ninguém negará que algoritmos e estruturas de dados são a base inegável da programação. Sim, você pode trabalhar como programador sem o conhecimento deles, mas, infelizmente, não irá longe. Portanto, para fortalecer sua base de conhecimento nesta área, gostaria de falar sobre uma estrutura de dados chamada pirâmide (também conhecida como heap e heap binário). Via de regra, tais estruturas de dados são utilizadas em diversos escalonadores e outras estruturas nas quais é necessário indicar a prioridade de diversas tarefas. Então... Uma pirâmide é um tipo de árvore que fornece inserção/exclusão em tempo O(logN) e possui as seguintes propriedades:

• Completude. Todos os níveis da árvore contêm todos os nós possíveis, exceto o último, que só pode ser preenchido parcialmente e que é preenchido da esquerda para a direita;
• Uma pirâmide geralmente é implementada com base em um array;
• Para cada nó da pirâmide existe uma condição fundamental de que o valor de cada nó seja maior (ou igual) aos valores de seus descendentes. Conseqüentemente, o máximo será armazenado no elemento superior.

Uma pirâmide que consiste em vértices que armazenam valores não superiores a 10: Gostaria de observar que, comparada a uma árvore de pesquisa binária, a pirâmide é fracamente ordenada , pois em uma árvore de pesquisa binária a chave do filho esquerdo é menor que a chave do filho certo, e em uma pirâmide não existe tal condição.

Removendo um elemento por índice

Primeiro, vejamos a sequência de ações ao excluir um nó selecionado:

1. Exclua o nó selecionado.
2. Mova o último nó da última linha para o lugar do excluído.
3. Mova-o para baixo até que esteja abaixo do nó maior e acima do nó menor.

Ao usar uma pirâmide, geralmente é necessário poder remover o topo (o elemento zero do array interno) ou o último (então as operações de movimentação podem ser omitidas, restando apenas a remoção do elemento). Como exemplo de exclusão de um elemento por índice na pirâmide que estamos vendo acima, excluiremos o nó com valor 7:

1. Excluímos o nó selecionado e colocamos o último em seu lugar, que tem valor 4:

   Mas nesta posição este nó não atende à condição de que cada nó descendente não seja maior que aquele em questão, certo?

   É por isso:

2. Trocamos com o maior dos filhos, que tem valor 6:

   A seguir, verificamos se há algum descendente com valor maior que o do nosso elemento deslocado e vemos que não há nenhum, o que significa que o elemento tomou o seu lugar.

Inserindo um novo elemento

Quais são as ações ao inserir um novo elemento:

1. O nó inserido é colocado no final da pirâmide.

   Mas temos a condição de que um elemento filho não pode ter um valor maior que seu pai, certo?

   É por isso:

2. Compare o novo elemento com o elemento pai. Se o novo elemento for menor, a operação será concluída; caso contrário, ele troca de lugar com o elemento pai. Depois disso, ele começa a ser comparado com o novo elemento pai, e assim por diante... Até que o elemento pai seja maior que o novo.

Por exemplo, à pirâmide obtida pela remoção de um elemento, queremos adicionar um elemento com o valor 8:

1. Coloque um novo nó no final da pirâmide:

2. Compare o novo elemento com o elemento pai, que tem o valor 4.

   Como o novo elemento é maior que o pai, nós os trocamos:

3. Comparamos o novo elemento com seu novo pai e vemos que nosso elemento é maior que seu (8>7), então os trocamos também:

   Novamente, comparamos o elemento com o elemento pai e vemos que desta vez o elemento pai é maior, o que significa que nosso novo elemento se encaixou.

Substituindo um elemento

Ao substituir um elemento, primeiro você precisa substituir o elemento pelo índice fornecido. Lógico, certo? Então, o que vem a seguir? Afinal, o novo valor do elemento já é diferente, e não é fato que corresponda às condições da pirâmide. Ou seja, não é fato que todos os elementos filhos sejam menores que o elemento inserido. Também não é fato que os elementos pais sejam maiores que o novo. Portanto, primeiro você precisa comparar com o valor antigo do elemento:

• se o novo elemento for maior que ele, precisamos compará-lo com os elementos pai e, se necessário, trocá-los;
• se o novo elemento for menor, ele deverá ser comparado com o maior dos elementos filhos e trocado se o elemento filho for maior (até que o novo elemento esteja em um local aceitável).

Vejamos isso usando nosso exemplo. Agora queremos inserir um elemento com valor 1 em vez de um elemento com valor 9:

1. Insira o elemento no lugar do anterior:
2. Comparamos o elemento anterior 9 e o novo 1 e vemos que ele é menor, o que significa que tentaremos deslocá-lo para baixo.
3. Comparamos com o maior elemento dos filhos, ou seja, com aquele que tem valor 5, e vemos que o novo é menor. Portanto, trocamos os elementos comparados:
4. Como agora não há novos elementos abaixo do nosso novo, podemos dizer que o elemento se encaixou.

Implementação de uma pirâmide em Java

Depois de entender como essa estrutura funciona, é hora de dar uma olhada na implementação de uma pirâmide em Java : Uma classe que representa um vértice e o valor que ele contém:

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

A classe que representa a própria pirâmide:

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

Finalmente, vamos dar uma olhada em nossa pirâmide em ação:

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

Saída do console:

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

Saída do console:

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

Saída do console: Bem, isso é tudo. Obrigado a todos pela atenção!