Məlumat Strukturları: Java-da Piramida (İkili Yığın).

Salam Salam! Heç kim inkar etməyəcək ki, alqoritmlər və məlumat strukturları proqramlaşdırmanın danılmaz əsasıdır. Bəli, siz onları bilmədən proqramçı kimi işləyə bilərsiniz, amma təəssüf ki, uzağa getməyəcəksiniz. Buna görə də, bu sahədə bilik bazanızı gücləndirmək üçün mən piramida adlanan məlumat strukturundan (həmçinin yığın və ikili yığın kimi tanınır) danışmaq istərdim . Bir qayda olaraq, bu cür məlumat strukturları müxtəlif planlaşdırıcılarda və müxtəlif tapşırıqların prioritetini göstərmək lazım olan digər strukturlarda istifadə olunur. Beləliklə... Piramida O(logN) zamanında daxiletmə/silməni təmin edən və aşağıdakı xüsusiyyətlərə malik olan ağac növüdür :

• Tamlıq. Ağacın bütün səviyyələri yalnız qismən doldurula bilən və soldan sağa doldurulan sonuncudan başqa bütün mümkün qovşaqları ehtiva edir;
• Piramida adətən massiv əsasında həyata keçirilir;
• Piramidadakı hər bir düyün üçün hər bir düyünün dəyərinin onun nəslinin dəyərlərindən böyük (və ya bərabər) olması üçün əsas şərt var. Müvafiq olaraq, maksimum yuxarı elementdə saxlanılacaq.

10-dan çox olmayan dəyərləri saxlayan təpələrdən ibarət piramida: Qeyd etmək istərdim ki, ikili axtarış ağacı ilə müqayisədə piramida zəif sıralanır , çünki ikili axtarış ağacında sol uşağın açarı kiçik olduğundan sağ uşağın açarı və piramidada belə bir şərt yoxdur.

Elementin indekslə silinməsi

Əvvəlcə seçilmiş qovşağı silərkən hərəkətlərin ardıcıllığına baxaq:

1. Seçilmiş qovşağı silin.
2. Sonuncu sətirdəki sonuncu qovşağı silinmiş yerə köçürün.
3. Böyük qovşağın altına və kiçik qovşağın üstünə gələnə qədər onu aşağı hərəkət etdirin.

Piramidadan istifadə edərkən, adətən, yuxarı hissəni (daxili massivin sıfır elementi) və ya sonuncunu (sonra yalnız elementin çıxarılmasını tərk edərək hərəkətli əməliyyatlar buraxıla bilər) çıxara bilmək lazımdır. Yuxarıda nəzərdən keçirdiyimiz piramidada elementi indekslə silməyə misal olaraq, dəyəri 7 olan qovşağı siləcəyik:

1. Seçilmiş qovşağı silirik və 4 dəyəri olan sonuncunu yerinə qoyuruq:

   Ancaq bu vəziyyətdə, bu qovşaq hər bir nəsil qovşağının sözügedənindən daha böyük olmaması şərtinə cavab vermir, elə deyilmi?

   Buna görə də:

2. Onu 6 dəyəri olan uşaqların ən böyüyü ilə dəyişdiririk:

   Sonra, biz yerdəyişmiş elementimizdən daha böyük dəyərə malik olan nəslin olub-olmadığını araşdırırıq və heç birinin olmadığını görürük, yəni element öz yerini tutur.

Yeni elementin daxil edilməsi

Yeni element daxil edərkən hansı hərəkətlər edilir:

1. Daxil edilmiş düyün piramidanın sonunda yerləşdirilir.

   Ancaq bir şərtimiz var ki, uşaq element öz anasından daha böyük dəyərə malik ola bilməz, elə deyilmi?

   Buna görə də:

2. Yeni elementi əsas elementlə müqayisə edin. Yeni element daha kiçikdirsə, əməliyyat tamamlanır, yoxsa, əsas element ilə yerləri dəyişdirir. Bundan sonra o, yeni ana elementlə müqayisə olunmağa başlayır və s... Ana element yenidən böyük olana qədər.

Məsələn, elementi silməklə əldə edilən piramidaya 8 dəyəri olan bir element əlavə etmək istəyirik:

1. Piramidanın sonunda yeni bir node qoyun:

2. Yeni elementi 4 dəyəri olan əsas elementlə müqayisə edin.

   Yeni element əsas elementdən daha böyük olduğundan, onları dəyişdiririk:

3. Biz yeni elementi onun yeni əsas elementi ilə müqayisə edirik və görürük ki, bizim element ondan (8>7) böyükdür, ona görə də onları dəyişdiririk:

   Yenə elementi ana elementlə müqayisə edirik və görürük ki, bu dəfə ana element daha böyükdür, yəni yeni elementimiz yerinə düşmüşdür.

Bir elementin dəyişdirilməsi

Elementi əvəz edərkən əvvəlcə elementi verilmiş indekslə əvəz etməlisiniz. Məntiqli, hə? Sonra nə olacaq? Axı elementin yeni qiyməti artıq fərqlidir və onun piramidanın şərtlərinə uyğun olması fakt deyil. Yəni bütün uşaq elementlərin daxil edilmiş elementdən kiçik olması fakt deyil. Ana elementlərin yenidən daha böyük olması da fakt deyil. Buna görə əvvəlcə elementin köhnə dəyəri ilə müqayisə etməlisiniz:

• yeni element ondan böyükdürsə, onda biz onu ana elementlərlə müqayisə etməliyik və lazım gələrsə, onları dəyişdirməliyik;
• yeni element daha kiçikdirsə, o, uşaq elementlərin daha böyüyü ilə müqayisə edilməli və uşaq element daha böyükdürsə (yeni element məqbul yerdə olana qədər) dəyişdirilməlidir.

Nümunəmizdən istifadə edərək buna baxaq. İndi biz 9 dəyəri olan elementin yerinə 1 dəyəri olan element daxil etmək istəyirik:

1. Elementi əvvəlki yerinə daxil edin:
2. Əvvəlki element 9 və yeni 1-i müqayisə edirik və onun daha kiçik olduğunu görürük, yəni onu aşağı salmağa çalışacağıq.
3. Biz onu uşaqlardan ən böyük elementlə, yəni dəyəri 5 olan elementlə müqayisə edirik və görürük ki, yenisi daha kiçikdir. Beləliklə, müqayisə olunan elementləri dəyişdiririk:
4. İndi bizim yeni elementimizin altında yeni elementlər olmadığı üçün elementin yerinə düşdüyünü deyə bilərik.

Java-da piramidanın həyata keçirilməsi

Bu strukturun necə işlədiyini başa düşdükdən sonra, Java-da piramidanın tətbiqinə baxmaq vaxtıdır : Bir təpəni və onun ehtiva etdiyi dəyəri təmsil edən sinif:

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

Piramidanın özünü təmsil edən sinif:

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

Nəhayət, piramidamızın fəaliyyətinə baxaq:

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

Konsol çıxışı:

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

Konsol çıxışı:

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

Konsol çıxışı: Bəli, hamısı budur. Diqqətiniz üçün hamınıza təşəkkür edirik!