Берилиштер структуралары: Java тилиндеги пирамида (экилик үймөк).

Салам Салам! Алгоритмдер жана маалымат структуралары программалоонун талашсыз негизи экенин эч ким танbyte. Ооба, сиз аларды билбей туруп программист болуп иштей аласыз, бирок тилекке каршы, сиз алыска бара албайсыз. Ошондуктан, бул чөйрөдө бorм базаңызды бекемдөө үчүн, мен пирамида деп аталган маалымат структурасы жөнүндө айткым келет (ошондой эле үймөк жана бинардык үймөк катары белгилүү). Эреже катары, мындай маалымат структуралары ар кандай пландаштыруучуларда жана ар кандай тапшырмалардын артыкчылыктуулугун көрсөтүү зарыл болгон башка структураларда колдонулат. Ошентип... Пирамида O(logN) убакытта киргизүүнү/жок кылууну камсыз кылган жана төмөнкү касиеттерге ээ болгон дарактын бир түрү:

• Толуктуулук. Дарактын бардык деңгээлдеринде акыркысынан башка бардык мүмкүн болгон түйүндөр камтылган, алар жарым-жартылай гана толтурулат жана солдон оңго карай толтурулат;
• Пирамида адатта массивдин негизинде ишке ашырылат;
• Пирамидадагы ар бир түйүн үчүн ар бир түйүндүн мааниси анын урпактарынын баалуулуктарынан чоң (же барабар) деген негизги шарт бар. Демек, максимум жогорку элементте сакталат.

10дон жогору эмес маанилерди сактаган чокулардан турган пирамида: бинардык издөө дарагына салыштырмалуу пирамида начар иреттелгендигин белгилегим келет , анткени бинардык издөө дарагында сол баланын ачкычы туура баланын ачкычы, ал эми пирамидада мындай шарт жок.

Элементти индекс боюнча алып салуу

Биринчиден, тандалган түйүндү жок кылууда аракеттердин ырааттуулугун карап көрөлү:

1. Тандалган түйүндү жок кылуу.
2. Акыркы саптагы акыркы түйүн жок кылынган жерге жылдырыңыз.
3. Чоңунан ылдый жана кичирээк түйүндөн жогору болмоюнча аны ылдый жылдырыңыз.

Пирамиданы колдонууда, адатта, үстүн (ички массивдин нөл элементи) же акыркысын (андан кийин элементти алып салуу гана калтырылып, кыймылдуу операцияларды өткөрүп жиберүүгө болот) алып салуу керек. Биз жогоруда карап жаткан пирамидадагы элементти индекс боюнча өчүрүүгө мисал катары, биз 7 мааниси бар түйүндү жок кылабыз:

1. Тандалган түйүндү жок кылабыз жана анын ордуна акыркысын коебуз, анын мааниси 4:

   Бирок бул позицияда бул түйүн ар бир тукум түйүн сөз болуп жаткандан чоң болбошу керек деген шартка жооп бербейт, туурабы?

   Ошол үчүн:

2. Биз аны балдардын эң чоңу менен алмаштырабыз, анын мааниси 6:

   Андан кийин, биз алмаштырылган элементибиздин маанисинен чоңураак урпактардын бар-жогун карап көрөлү жана алардын жок экенин көрөбүз, бул элемент өз ордун ээледи дегенди билдирет.

Жаңы элемент киргизүү

Жаңы элементти киргизүүдө кандай аракеттер болот:

1. Киргизилген түйүн пирамиданын аягында жайгаштырылат.

   Бирок бизде бала элементтин ата-энесинен чоңураак мааниге ээ болушу мүмкүн эмес деген шарт бар, туурабы?

   Ошол үчүн:

2. Жаңы элементти негизги элемент менен салыштырыңыз. Эгерде жаңы элемент кичине болсо, анда операция аяктады, эгерде жок болсо, анда ал негизги элемент менен орундарды алмаштырат. Андан кийин, ал жаңы негизги элемент менен салыштырыла баштайт жана башкалар... Аталык элемент жаңыдан чоңураак болмоюнча.

Мисалы, элементти алып салуу менен алынган пирамидага биз 8 мааниси бар элементти кошкубуз келет:

1. Пирамиданын аягына жаңы түйүн коюңуз:

2. Жаңы элементти 4 мааниси бар негизги элемент менен салыштырыңыз.

   Жаңы элемент ата-энеден чоңураак болгондуктан, биз аларды алмаштырабыз:

3. Жаңы элементти анын жаңы ата-энеси менен салыштырып, биздин элемент андан чоңураак экенин көрөбүз (8>7), ошондуктан аларды да алмаштырабыз:

   Дагы эле, биз элементти негизги элемент менен салыштырып көрөбүз жана бул жолу ата-энелик элемент чоңураак экенин көрөбүз, бул биздин жаңы элементибиз ордуна түшүп калганын билдирет.

Элементти алмаштыруу

Элементти алмаштырууда алгач элементти берилген индекс менен алмаштыруу керек. Логикалык, туурабы? Анан эмне болот? Анткени, элементтин жаңы мааниси буга чейин эле башкача, ал пирамиданын шарттарына туура келгени чындык эмес. Башкача айтканда, бардык кошумча элементтер киргизилген элементтен кичине экендиги чындык эмес. Ата-энелик элементтер жаңыдан чоңураак экени да чындык эмес. Ошондуктан, адегенде элементтин эски мааниси менен салыштыруу керек:

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

Муну биздин мисал аркылуу карап көрөлү. Эми биз 9 мааниси бар элементтин ордуна 1 мааниси бар элементти киргизгибиз келет:

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; // номер 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
  }
}

Акырында, келгиле, пирамидабызды карап көрөлү:

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, который имеет meaning 80 и смотрим на изменившуюся пирамиду
     heap.removeNode(3);
     heap.printHeap();
  }
}

Консолдун чыгышы: Ооба, ушунча. Көңүл бурганыңыздар үчүн рахмат!