Maglumatlaryň gurluşlary: Java-da piramida (Binary Heap)

Salam Salam! Algoritmleriň we maglumatlar gurluşlarynyň programmirlemegiň inkär edip bolmajak esasydygyny hiç kim inkär etmez. Hawa, olary bilmän programmist bolup işläp bilersiňiz, ýöne gynansak-da, uzaklaşyp bilmersiňiz. Şonuň üçin bu ugurdaky bilim binýadyňyzy berkitmek üçin piramida (üýşmek we ikilik üýşmesi hem diýilýär) atly maglumat gurluşy barada gürleşmek isleýärin . Düzgün bolşy ýaly, şular ýaly maglumat gurluşlary dürli meýilnamalarda we dürli meseleleriň ileri tutulýandygyny görkezmek zerur bolan beýleki gurluşlarda ulanylýar. Şonuň üçin ... Piramida O (logN) wagtynda goýulmagy / ýok edilmegini üpjün edýän we aşakdaky häsiýetlere eýe bolan agaç görnüşidir :

• Doly Agajyň ähli derejelerinde diňe bölekleýin dolduryp bolýan we çepden saga doldurylan iň soňky düwmeden başga ähli mümkin düwünler bar;
• Piramida, adatça, bir massiw esasynda amala aşyrylýar;
• Piramidadaky her düwün üçin her düwüniň bahasynyň nesilleriniň gymmatlyklaryndan (ýa-da deňdir) esasy şerti bar. Şoňa laýyklykda iň ýokary element ýokarky elementde saklanar.

Gymmatlyklaryny 10-dan ýokary bolmadyk dikliklerden ybarat piramida: Ikilik gözleg agajy bilen deňeşdirilende piramidanyň gowşak sargyt edilendigini belläsim gelýär , sebäbi ikilik gözleg agajynda çep çaganyň açary azdyr dogry çaganyň açary, piramida bolsa beýle ýagdaý ýok.

Bir elementi indeks boýunça aýyrmak

Ilki bilen, saýlanan düwün öçürilende hereketleriň yzygiderliligine seredeliň:

1. Saýlanan düwmäni pozuň.
2. Iň soňky hatardaky iň soňky düwmäni öçürilen ýerine geçiriň.
3. Ulydan aşakda we kiçi düwüniň üstünde bolýança aşak süýşüriň.

Piramida ulanylanda, adatça ýokarsyny (içerki massiwiň nol elementi) ýa-da iň soňkusyny aýyrmagy başarmaly (soň hereket edýän amallar diňe elementiň aýrylmagyny goýup biler). Aboveokarda seredýän piramida indeks boýunça bir elementi pozmagyň mysaly hökmünde düwmäni 7 bahasy bilen pozarys:

1. Saýlanan düwmäni pozýarys we iň soňkusyny 4 bahasy bolan ýerine goýýarys:

   Thisöne bu ýagdaýda bu düwün her nesil düwüniniň sorag edilýäninden uly bolmaly däldigine laýyk gelmeýär, şeýlemi?

   Şonuň üçin:

2. 6 bahasy bolan çagalaryň iň ulusy bilen çalyşýarys:

   Ondan soň, göçürilen elementimizden has gymmaty bolan nesilleriň bardygyny ýa-da ýokdugyny görýäris we ýoklugyna göz ýetirýäris, bu elementiň ýerini alandygyny aňladýar.

Täze element goýmak

Täze element girizilende haýsy hereketler bar:

1. Goýlan düwün piramidanyň ujunda ýerleşdirildi.

   Weöne çaga elementiniň ene-atasyndan has uly gymmaty bolmazlygy şerti bar, şeýlemi?

   Şonuň üçin:

2. Täze elementi esasy element bilen deňeşdiriň. Täze element has kiçi bolsa, amal gutarýar; ýok bolsa, esasy element bilen ýerleri çalyşýar. Ondan soň, täze ene elementi we ş.m. bilen deňeşdirip başlaýar ... Esasy element täze elementden uly bolýança.

Mysal üçin, bir elementi aýyrmak bilen alnan piramida 8 bahasy bolan bir element goşmak isleýäris:

1. Piramidanyň ujuna täze düwün goýuň:

2. Täze elementi 4 bahasy bolan esasy element bilen deňeşdiriň.

   Täze element ene-atadan has uly bolansoň, olary çalyşýarys:

3. Täze elementi täze ene-atasy bilen deňeşdirýäris we elementimiziň (8> 7) uludygyny görýäris, şonuň üçinem olary çalyşýarys:

   Againene-de elementi esasy element bilen deňeşdirýäris we bu gezek esasy elementiň has uludygyny görýäris, bu bolsa täze elementimiziň ýerine düşendigini aňladýar.

Bir elementi çalyşmak

Bir elementi çalyşanyňyzda ilki bilen elementi berlen indeks bilen çalyşmaly. Mantykly, şeýlemi? Ondan soň näme? Galyberse-de, elementiň täze gymmaty eýýäm başga, piramidanyň şertlerine laýyk gelýändigi hakykat däl. Childagny, ähli çaga elementleriniň goýlan elementden kiçi bolmagy hakykat däl. Şeýle hem, esasy elementleriň täzesinden has uludygy hakykat däl. Şonuň üçin ilki bilen elementiň köne bahasy bilen deňeşdirmeli:

• täze element ondan uly bolsa, onda ony esasy elementler bilen deňeşdirmeli we zerur bolsa çalyşmaly;
• täze element kiçi bolsa, ony çaga elementleriniň has ulusy bilen deňeşdirmeli we çaga elementi has uly bolsa (täze element kabul ederlikli ýerde bolýança) çalşylmaly.

Geliň, mysalymyzy ulanyp seredeliň. Indi 9 bahaly elementiň ýerine 1 bahaly element goýmak isleýäris:

1. Elementi öňki ýerine goýuň:
2. Öňki element 9 bilen täzesini 1 deňeşdirýäris we onuň kiçidigini görýäris, bu bolsa ony aşak süýşürmäge synanyşarys.
3. Çagalaryň iň uly elementi, ýagny 5 bahasy bolan element bilen deňeşdirýäris we täzesiniň kiçidigini görýäris. Şonuň üçin deňeşdirilen elementleri çalyşýarys:
4. Indi täze elementimiziň aşagynda täze elementler ýoklugy sebäpli, elementiň ýerine düşendigini aýdyp bileris.

Java-da piramidany ornaşdyrmak

Bu gurluşyň nähili işleýändigine düşünenimizden soň, Java-da piramidanyň ýerine ýetirilişine göz aýlamagyň wagty geldi : Bir sözlemi we içindäki bahany görkezýän synp:

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

Piramidanyň özüni görkezýän synp:

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

Ahyrynda, piramidamyza hereket edeliň:

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 çykyşy:

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

Konsol çykyşy:

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

Konsol çykyşy: Bolýar. Üns bereniňiz üçin hemmäňize sag bolsun aýdýaryn!