Структуры данных: пирамида (двоичная куча) в Java

Привет-привет! Никто не будет отрицать, что алгоритмы и структуры данных — неоспоримый фундамент программирования. Да, можно и работать программистом и без их знания, но увы, далеко вы так не уедете. Поэтому чтобы усилить вашу базу знаний в этой области, хотелось бы поговорить о такой структуре данных как пирамида (еще известная как куча и двоичная куча). Как правило такие структуры данных применяют в различных планировщиках и других структурах, в которых нужно обозначить приоритетность различных задач. Итак...Пирамида — это разновидность дерева, которая обеспечивает вставку/удаление за время O(logN) и обладает следующими свойствами:

• Полнота. Все уровни дерева содержат все возможные узлы, кроме последнего, который может быть заполнен лишь частично и который заполняется слева-направо;
• Пирамида как правило реализуется на базе массива;
• Для каждого узла в пирамиде есть основополагающее условие, что значение каждого узла больше (или равно) значениям его потомков. Соответственно, максимум будет храниться в верхнем элементе.

Пирамида, состоящая из вершин, которые хранят значения не выше 10:Хотелось бы отметить, что по сравнению с деревом двоичного поиска пирамида является слабо упорядоченной, так как в дереве двоичного поиска ключ левого потомка меньше ключа правого потомка, а в пирамиде такое условие отсутствует.

Удаление элемента по индексу

Для начала давайте рассмотрим, какова же последовательность действий при удалении выбранного узла:

1. Удалить выбранный узел.
2. Переместить последний узел, в последнем ряду на место удаленного.
3. Смещать его вниз до тех пор, пока он не окажется ниже большего и выше меньшего узла.

Когда используют пирамиду, то как правило необходимо уметь удалять вершину (нулевой элемент внутреннего массива) или последний (тогда операции по перемещению можно опустить, оставив только удаление элемента). В качестве примера удаления элемента по индексу в рассматриваемой нами пирамиде выше мы удалим узел со значением 7:

1. Удаляем выбранный узел и помещаем на его место последний, который у нас имеет значение 4:

   Но в таком положении данный узел не соответствует условию, что каждый узел потомок не должен быть больше рассматриваемого, не так ли?

   Поэтому:

2. Меняем его местами с наибольшим из потомков, который имеет значение 6:

   Далее смотрим, нет ли потомков со значением большим, чем у нашего смещаемого элемента, и видим что нет, а это значит, что элемент стал на свое место.

Вставка нового элемента

Каковы же действия при вставке нового элемента:

1. Вставляемый узел помещается в конец пирамиды.

   Но ведь у нас же есть условие, что дочерний элемент не может иметь значение больше родительского, верно?

   Поэтому:

2. Сравниваем новый элемент с родительским элементом. Если новый элемент меньше, то операция закончена, если нет, то он меняется местами с родительским элементом. После — начинает сравниваться с новым родительским элементом, и так далее... До тех пор, пока родительский элемент не будет больше нового.

К примеру, в пирамиду, которая была получена в результате удаления элемента, мы хотим добавить элемент со значением 8:

1. Помещаем новый узел в конец пирамиды:

2. Сравниваем новый элемент с родительским элементом, который имеет значение 4.

   Так как новый элемент больше родительского, меняем их местами:

3. Сравниваем новый элемент с новым его родителем и видим, что наш элемент больше и его (8>7), поэтому меняем местами и их:

   Опять же, сравниваем элемент с родительский элементом и видим, что в этот раз родительский элемент больше, а это значит что наш новый элемент стал на свое место.

Замена элемента

При замене элемента сперва нужно заменить элемент с заданным индексом. Логично, не так ли? Ну а что далее? Ведь новое значение элемента уже другое, и не факт, что оно соответствует условию пирамиды. То есть не факт что все дочерние элементы меньше вставляемого элемента. Также не факт, что родительские элементы больше нового. Поэтому сперва нужно сравнить со старым значением элемента:

• если новый элемент больше, чем он, то нам нужно сравнивать его с родительскими элементами и при надобности менять их местами;
• если же новый элемент меньше, то нужно сравнивать с большим из дочерних элементов и менять местами, если дочерний элемент окажется больше (до тех пор, пока новый элемент не станет на допустимое место).

Давайте же это рассмотрим на нашем примере. Сейчас мы хотим вставить элемент со значением 1 вместо элемента со значением 9:

1. Вставляем элемент на место предыдущего:
2. Сравниваем предыдущий элемент 9 и новый 1 и видим, что меньше, а значит, мы будем пробовать смещать вниз.
3. Сравниваем с большим элементом из дочерних, то есть с тем, который имеет значение 5, и видим, что новый меньше. Поэтому меняем сравниваемые элементы местами:
4. Так как сейчас новых элементов ниже нашего нового уже нет, можно сказать, что элемент встал на свое место.

Реализация пирамиды на Java

После понимания принципа работы данной структуры самое время рассмотреть реализацию пирамиды на Java: Класс, представляющий одну вершину и значение, которое она содержит:

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

Класс, представляющий саму пирамиду:

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; // номер элемента в данной строке
     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());// выводим в консоль значение вершины
       
        if (++columnNumber == itemsPerRow) { // проверяем последний ли элемент в строке
           countOfGaps /= 2; // уменьшаем количество оступов применяемое для следующей строки
           itemsPerRow *= 2; // указываем, что элементов может быть вдвое больше
           columnNumber = 0; // сбрасываем счётчик для текущего элемента строки
           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);// создание вершины с данным значением
     heapArray[currentSize] = newNode;// вершину задём в самый низ дерева
     displaceUp(currentSize++);// пытаемся поднять вершину, если значение вершины позволяет
     return true;
  }
 
  public Node removeNode(int index) { // удалить элемент по индексу массива
     if(index > 0 && currentSize > index) {
        Node root = heapArray[index];
        heapArray[index] = heapArray[--currentSize]; // задаём элементу с переданным индексом, значение последнего элемента
        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(); // сохраняем старое значение
     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) {// если данное условие не выполняется то элемент уже в самом низу пирамиды
        int leftChild = 2 * index + 1; // вычисляем индексы в массиве для левого узла ребенка
        int rightChild = leftChild + 1;// и правого
       
        if (rightChild < currentSize && heapArray[leftChild].getValue() < heapArray[rightChild].getValue()) {
           largerChild = rightChild;
        }// вычисляем ребенка вершину с наибольшим числовым значением
        else {
           largerChild = leftChild;
        }
       
        if (top.getValue() >= heapArray[largerChild].getValue()) {// если значение вершины больше или равно
           //значени его наибольшего ребенка
           break;// то выходим из метода
        }
       
        heapArray[index] = heapArray[largerChild];// заменяем вершину, большей дочерней вершиной
        index = largerChild; // текущий индекс переходит вниз
     }
     heapArray[index] = top; // задаем конечное местоположение для элемента
  }
}

И наконец, давайте посмотрим на нашу пирамиду в деле:

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

Вывод в консоли:

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

Вывод в консоли:

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

Вывод в консоли:Ну вот, собственно, и всё. Всем спасибо за внимание!