Структури даних: піраміда (двійкова купа) у 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();
  }
}

Висновок у консолі: Ну от, власне, і все. Всім дякую за увагу!