Деректер құрылымдары: Java тіліндегі пирамида (екілік үйме).

Сәлем Сәлем! Алгоритмдер мен деректер құрылымдары бағдарламалаудың даусыз негізі екенін ешкім жоққа шығармайды. Иә, сіз оларды білмей-ақ бағдарламашы ретінде жұмыс істей аласыз, бірақ өкінішке орай, сіз алысқа бара алмайсыз. Сондықтан, осы саладағы білім қорыңызды нығайту үшін мен пирамида деп аталатын деректер құрылымы (үйме және екілік үйме ретінде де белгілі) туралы айтқым келеді . Әдетте, мұндай деректер құрылымдары әртүрлі жоспарлаушыларда және әртүрлі тапсырмалардың басымдылығын көрсету қажет басқа құрылымдарда қолданылады. Сонымен... Пирамида – 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();
  }
}

Консоль шығысы: Барлығы осы. Назарларыңызға барлығыңызға рахмет!