Data Structures: Pyramid (Binary Heap) in Java

Hi Hi! No one will deny that algorithms and data structures are the undeniable foundation of programming. Yes, you can work as a programmer without knowing them, but alas, you won’t get far. Therefore, to strengthen your knowledge base in this area, I would like to talk about a data structure called a pyramid (also known as heap and binary heap). As a rule, such data structures are used in various schedulers and other structures in which it is necessary to indicate the priority of various tasks. So... A pyramid is a type of tree that provides insertion/deletion in O(logN) time and has the following properties:

• Completeness. All levels of the tree contain all possible nodes except the last one, which can only be partially filled and which is filled from left to right;
• A pyramid is usually implemented based on an array;
• For each node in the pyramid, there is a fundamental condition that the value of each node is greater than (or equal to) the values ​​of its descendants. Accordingly, the maximum will be stored in the top element.

A pyramid consisting of vertices that store values ​​no higher than 10: I would like to note that compared to a binary search tree, a pyramid is weakly ordered , since in a binary search tree the key of the left child is less than the key of the right child, and in a pyramid there is no such condition.

Removing an element by index

First, let's look at the sequence of actions when deleting a selected node:

1. Delete the selected node.
2. Move the last node in the last row to the place of the deleted one.
3. Move it down until it is below the larger and above the smaller node.

When using a pyramid, it is usually necessary to be able to remove the top (the zero element of the internal array) or the last one (then the moving operations can be omitted, leaving only the removal of the element). As an example of deleting an element by index in the pyramid we're looking at above, we'll delete the node with value 7:

1. We delete the selected node and place the last one in its place, which has a value of 4:

   But in this position, this node does not meet the condition that each descendant node should not be larger than the one in question, right?

   That's why:

2. We swap it with the largest of the children, which has a value of 6:

   Next, we look to see if there are any descendants with a value greater than that of our displaced element, and we see that there are none, which means that the element has taken its place.

Inserting a new element

What are the actions when inserting a new element:

1. The inserted node is placed at the end of the pyramid.

   But we have a condition that a child element cannot have a value greater than its parent, right?

   That's why:

2. Compare the new element with the parent element. If the new element is smaller, then the operation is completed; if not, then it swaps places with the parent element. After that, it begins to be compared with the new parent element, and so on... Until the parent element is greater than the new one.

For example, to the pyramid that was obtained by removing an element, we want to add an element with the value 8:

1. Place a new node at the end of the pyramid:

2. Compare the new element with the parent element, which has a value of 4.

   Since the new element is larger than the parent, we swap them:

3. We compare the new element with its new parent and see that our element is larger than its (8>7), so we swap them too:

   Again, we compare the element with the parent element and see that this time the parent element is larger, which means that our new element has fallen into place.

Replacing an element

When replacing an element, you first need to replace the element with the given index. Logical, right? So what next? After all, the new value of the element is already different, and it is not a fact that it corresponds to the conditions of the pyramid. That is, it is not a fact that all child elements are smaller than the inserted element. It is also not a fact that the parent elements are larger than the new one. Therefore, you first need to compare with the old value of the element:

• if the new element is larger than it, then we need to compare it with the parent elements and, if necessary, swap them;
• if the new element is smaller, then it must be compared with the larger of the child elements and swapped if the child element is larger (until the new element is in a valid place).

Let's look at this using our example. Now we want to insert an element with value 1 instead of an element with value 9:

1. Insert the element in place of the previous one:
2. We compare the previous element 9 and the new one 1 and see that it is smaller, which means we will try to shift it down.
3. We compare it with the largest element from the children, that is, with the one that has a value of 5, and we see that the new one is smaller. Therefore, we swap the compared elements:
4. Since now there are no new elements below our new one, we can say that the element has fallen into place.

Implementation of a pyramid in Java

After understanding how this structure works, it's time to look at the implementation of a pyramid in Java : A class representing one vertex and the value it contains:

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

The class representing the pyramid itself:

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

Finally, let's look at our pyramid in 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();

Console output:

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

Console output:

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

Console output: Well, that's all. Thank you all for your attention!